블록 이동하기

from queue import deque N = -1 A = None def is_valid(r1, c1, r2=None, c2=None): if r2 is not None and c2 is not None: tmp = (0 <= r1 < N) and (0 <= c1 < N) and (0 <= r2 < N) and (0 <= c2 < N) return tmp and A[r1][c1] == 0 and A[r2][c2] == 0 else: return (0 <= r1 < N) and (0 <= c1 < N) and A[r1][c1] == 0 def solution(board): global N, A N = len(board) A = board # 복잡해 보이지만, 상하좌우 이동 4가지, # 왼쪽/오른쪽 혹은 위쪽/아래쪽 축으로 시계/반시계 회전 4가지 총 8가지 # 움직임이 있는 bfs로 해결해봅니다. q, vis = deque(), set() # (d, r1, c1, r2, c2)를 큐에 넣습니다. # 항상 r1 <= r2, c1 <= c2가 되도록 합니다. q.append( (0, 0, 0, 0, 1) ) vis.add( (0, 0, 0, 1) ) while q: d, r1, c1, r2, c2 = q.popleft() # 목적지에 도달했으면 이동 거리를 리턴합니다. if r2 == N-1 and c2 == N-1: return d # 평행이동 # r1, c1, r1, c2의 대소 관계가 보존됩니다. moves = [ # dr1, dc1, dr2, dc2 (0, 1, 0, 1), # 오른쪽 (0, -1, 0, -1), # 왼쪽 (-1, 0, -1, 0), # 위쪽 (1, 0, 1, 0), # 아래쪽 ] for dr1, dc1, dr2, dc2 in moves: state = (r1+dr1, c1+dc1, r2+dr2, c2+dc2) if is_valid(*state) and state not in vis: q.append( (d+1, *state) ) vis.add(state) # 회전 # 1. 가로로 놓여있는 경우 if r1 == r2: # 1-1. 왼쪽 축, 반시계방향 회전 state = (r2-1, c2-1, r1, c1) if is_valid(*state) and state not in vis and is_valid(r2-1, c2): q.append( (d+1, *state) ) vis.add(state) # 1-2. 왼쪽 축, 시계방향 회전 state = (r1, c1, r2+1, c2-1) if is_valid(*state) and state not in vis and is_valid(r2+1, c2): q.append( (d+1, *state) ) vis.add(state) # 1-3. 오른쪽 축, 시계방향 회전 state = (r1-1, c1+1, r2, c2) if is_valid(*state) and state not in vis and is_valid(r1-1, c1): q.append( (d+1, *state) ) vis.add(state) # 1-4. 오른쪽 축, 반시계방향 회전 state = (r2, c2, r1+1, c1+1) if is_valid(*state) and state not in vis and is_valid(r1+1, c1): q.append( (d+1, *state) ) vis.add(state) # 2. 세로로 놓인 경우 else: # 2-1. 위쪽 축, 시계방향 회전 state = (r2-1, c2-1, r1, c1) if is_valid(*state) and state not in vis and is_valid(r1+1, c1-1): q.append( (d+1, *state) ) vis.add(state) # 2-2. 위쪽 축, 반시계방향 회전 state = (r1, c1, r2-1, c2+1) if is_valid(*state) and state not in vis and is_valid(r1+1, c1+1): q.append( (d+1, *state) ) vis.add(state) # 2-3. 아래쪽 축, 시계방향 회전 state = (r2, c2, r1+1, c1+1) if is_valid(*state) and state not in vis and is_valid(r2-1, c2+1): q.append( (d+1, *state) ) vis.add(state) # 2-4. 아래쪽 축, 반시계방향 회전 state = (r1+1, c1-1, r2, c2) if is_valid(*state) and state not in vis and is_valid(r2-1, c2-1): q.append( (d+1, *state) ) vis.add(state)