[Python/파이썬] 백준 1726번: 로봇

문제 풀이 왼쪽 오른쪽 설정 def turnLeft(now): if now == 1: return 4 #동 북 if now == 2: return 3 #서 남 if now == 3: return 1 #남 동 if now == 4: return 2 #북 서 def turnRight(now): if now == 1: return 3 #동 남 if now == 2: return 4 #서 북 if now == 3: return 2 #남 서 if now == 4: return 1 #북 동 입력 i, j, dir은 로봇의 위치 m, n = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(m)] visited = [[[..

[Python/파이썬] 백준 3055번: 탈출

문제 풀이 입력받는 코드 from collections import deque input = __import__('sys').stdin.readline r, c = map(int, input().split()) graph = [list(input().strip()) for _ in range(r)] waterVisited = [[False] * c for _ in range(r)] dociVisited = [[False] * c for _ in range(r)] water = deque() dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] 굴, 고슴도치, 물의 위치를 찾아주었다. 물 같은 경우 bfs를 수행해야 하므로 deque에 넣었다. # 초기값 설정 for i in range(r)..

[Python/파이썬] 백준 16933번: 벽 부수고 이동하기 3

문제 풀이 n, m, k = map(int, input().split()) graph = [input().rstrip() for _ in range(n)] visited = [[k + 1 for _ in range(m)] for _ in range(n)] visited[0][0] = 0 visited는 도착했을 때 벽을 부순 횟수를 넣는다. 초기 값으로 벽을 최대로 부술 수 있는 횟수를 넣는다. 만약 (x, y) 좌표에서 벽을 부순 횟수(w)가 5번이고, k+1 = 7이라고 가정했을 때 visited[y][x] = 4 인 경우 (x, y) 좌표에 벽을 4번 부수고 방문했다는 뜻 visited[y][x] = 7인 경우 (x, y) 좌표를 아직 방문하지 않았다는 뜻 코드 from collections imp..

[Python/파이썬] 백준 16946번: 벽 부수고 이동하기 4

문제 풀이 1. 0의 묶음을 그룹으로 표시해준다. 2. 각 그룹별로 0의 개수가 몇 개인지 dict를 통해 저장한다. 3. 벽(1)에서 상하좌우로 인접한 그룹을 구한 뒤, 그 그룹에 해당하는 0의 개수를 더해준다. 그룹이 중복되지 않게 set()을 사용한다. 코드 from collections import deque input = __import__('sys').stdin.readline def bfs(start): q = deque() q.append(start) cnt = 1 while q: i, j = q.popleft() zeros[i][j] = group for idx in range(4): ni, nj = i + dy[idx], j + dx[idx] if ni = n or ..

[Python/파이썬] 백준 16954번: 움직이는 미로 탈출

문제 풀이 벽이 한 칸 내려오는 것 = 욱제가 한 칸 위로 올라가는 것 또한 욱제가 맨 위칸으로 올라가기만 하면, 가장 오른쪽으로 갈 수 있다. (1초 뒤에는 욱제와 같은 칸에 있는 벽들이 전부 아래로 내려가고, 욱제는 그 칸에 그대로 있으므로) 코드 from collections import deque input = __import__('sys').stdin.readline n = 8 graph = [list(input().strip()) for _ in range(n)] visited = [[False] * n for _ in range(n)] dx = [0, 0, 1, -1, 1, -1, 1, -1, 0] dy = [1, -1, 0, 0, 1, 1, -1, -1, 0] q = deque() q.ap..

[Python/파이썬] 백준 2448번: 별 찍기 - 11

문제 풀이 위 그림과 통해 규칙을 알 수 있다. N = 6 -> N = 3일 때의 삼각형 3개로 분할 가능 N = 12 -> N = 6일 때의 삼각형 3개로 분할 가능 N = 24 -> N = 6일 때의 삼각형 3개로 분할 가능 ... N= 3인 경우 삼각형을 그린다. 아닐 경우, 이전 상태의 삼각형(N//2) 3개로 분할 (각각에 대해 재귀 호출) 1. 우선 전체 배열을 생성 stars = [[' ']*2*n for _ in range(n)] 2. 분할 정복을 위해 함수 생성 후 n이 3일 때 삼각형을 그려준다. i, j는 좌표 값 def recursion(i, j, size): if size == 3: stars[i][j] = '*' stars[i + 1][j - 1] = stars[i + 1][j ..

[Python/파이썬] 백준 1043번: 거짓말

문제 풀이 진실을 알고 있는 사람의 집합을 knowList 파티에 참석한 사람의 집합을 party party를 원소로 갖는 배열 parties 1. 만약 party, knowList의 교집합이 하나라도 있으면 knowList = knowList.union(party) (파티에 진실을 아는 사람이 한 명이라도 있다면, 그 사람으로 인해 파티에 참석한 모든 사람이 진실을 알게 됨) 2. 위 과정을 파티의 수만큼 반복 why?? 5개의 파티가 있고 진실을 아는 사람이 A라고 가정하자. 이 경우 5개의 파티 중 A가 참여한 파티가 있는지 확인하면 된다. 확인하던 도중 A가 3번째 파티에 참여한 것이 발견되어 B 역시 진실을 알게 되었다고 가정하자. B에 대해서도 마찬가지로 5개의 파티 중 B가 참여한 파티가 있..

[Python/파이썬] 백준 10830번: 행렬 제곱

문제 풀이 행렬 곱셈을 구하는 함수만 작성하면 분할 제곱을 이용한 거듭제곱 알고리즘을 통해 쉽게 풀 수 있다. 행렬 곱셈을 구하는게 좀 까다로웠다... 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 9) n, b = map(int, input().split()) matrix = [] for _ in range(n): matrix.append(list(map(int, input().split()))) def mulMatrix(m1, m2): tmpArr = [[] for _ in range(n)] for i in range(n): for j in range(n): tmp = 0 for k in range(n): tmp += m1[..

[Python/파이썬] 백준 13116번: 30번

문제 풀이 완전 이진트리 및 LCA 문제이다. 완전 이진트리의 레벨은 log2를 통해 구할 수 있고 부모는 /2를 해주면 된다. 즉 두 노드의 레벨을 구한 뒤, 레벨을 서로 같게 맞춰준 뒤, 두 노드가 서로 같을 때까지 각 노드에 /2를 해주면 된다. (이진트리와 LCA를 공부하면 쉽게 풀 수 있다.) 코드 import sys, math input = sys.stdin.readline t = int(input()) def getLevel(n): return math.floor(math.log2(n)) for _ in range(t): a, b = map(int, input().split()) while True: levelA, levelB = getLevel(a), getLevel(b) if levelA..

[Python/파이썬] 백준 11054번: 가장 긴 바이토닉 부분 수열

문제 풀이 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 구하면 된다. (부분 수열 시리즈를 풀었다면 쉽게 풀 수 있다.) 코드 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dpMax = [1] * n dpMin = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]: dpMax[i] = max(dpMax[i], dpMax[j] + 1) for i in range(n - 1, -1, -1): for j in range(i, n): if arr[i] > arr[j]: dpMin[i] = max(dpMin..