[Programmers] 블록 이동하기 문제 풀이 (Python)

1. 문제 풀이

BFS를 이용해 최단거리를 찾는 문제이다.

일반적인 BFS문제와는 몇 가지 차이점이 존재했는데,

• 한 번에 2칸씩 차지하면서 이동
• 상하좌우 이동 + 90도 회전

한 번에 2칸씩 차지하면서 이동하는 것은 구현하는데 크게 어렵지 않았지만 90도 회전을 구현하는 것이 까다로웠다.

최종

• visited를 3차원으로 만들어서 가로 또는 세로로 들어오는 경우가 겹치지 않도록 체크했다
  • visited[i][j][0]: 가로로 들어온 경우, visited[i][j][1]: 세로로 들어온 경우
• 상하좌우 이동은 1칸씩 차지할 때를 2칸씩 차지할 때로 변경해서 구현하였다.
  • 방문 체크(중복 제거)를 주의해야한다.
  • visited[dy1][dx1][direc] and visited[dy2][dx2][direc]이 True일 때를 제외하고는 상하좌우로 움직일 수있다.(dy1,dx1,dy2,dx2 ⇒ 이동하는 곳의 좌표, direc ⇒ 가로(0) 또는 세로(1))
• 가로 방향일 때와 세로 방향일 때 회전하는 방법이 다르기 때문에 회전하는 코드를 하나의 함수로 만들지 않고 각각을 따로 만들었다.
  • 그림을 통해 회전할 때 어떤 좌표로 이동하는지 확인해보면 구현하기 쉽다.

2. 코드

최종 개선 코드

from collections import deque

my = [1,-1,0,0]
mx = [0,0,1,-1]

def solution(board):
    N = len(board)
    visited = [[[0] * 2 for _ in range(N)] for _ in range(N)]
    visited[0][0][0] = 1
    visited[0][1][0] = 1
    q = deque([(0,0,0,1,0,0)])
    while q:
        y1,x1,y2,x2,cnt, direc = q.popleft()
        if (y1, x1) == (N - 1, N - 1) or (y2, x2) == (N - 1, N - 1):
            return cnt

        for i in range(4):
            dy1,dx1,dy2,dx2 = y1 + my[i], x1 + mx[i], y2 + my[i], x2 + mx[i]
            if not (0 <= dy1 < N and 0 <= dx1 < N and 0 <= dy2 < N and 0 <= dx2 < N): continue
            if board[dy1][dx1] or board[dy2][dx2]: continue
            if (visited[dy1][dx1][direc] and visited[dy2][dx2][direc]): continue

            visited[dy1][dx1][direc] = 1
            visited[dy2][dx2][direc] = 1
            q.append((dy1, dx1, dy2, dx2, cnt + 1, direc))

        if direc == 0:
            for ny1,nx1,ny2,nx2 in [(y1,x1,y2,x2),(y2,x2,y1,x1)]:
                for i in [1,-1]:
                    if ny1 - i < 0 or ny1 - i >= N: continue
                    if board[ny2-i][nx2] or board[ny1-i][nx1] or visited[ny1-i][nx1][1]: continue

                    visited[ny1-i][nx1][1] = 1
                    visited[ny1][nx1][1] =1
                    if ny1-i > ny1:
                        q.append((ny1,nx1,ny1-i,nx1,cnt+1,1))
                    else:
                        q.append((ny1-i,nx1,ny1,nx1,cnt+1,1))
        else:
            for ny1, nx1, ny2, nx2 in [(y1, x1, y2, x2), (y2, x2, y1, x1)]:
                for i in [1, -1]:
                    if nx1 - i < 0 or nx1 - i >= N: continue
                    if board[ny2][nx2-i] or board[ny1][nx1-i] or visited[ny1][nx1-i][0]: continue

                    visited[ny1][nx1-i][0] = 1
                    visited[ny1][nx1-i][0] = 1
                    if nx1 - i > nx1:
                        q.append((ny1, nx1, ny1, nx1-i, cnt + 1, 0))
                    else:
                        q.append((ny1, nx1-i, ny1, nx1, cnt + 1, 0))
    return -1

처음에는 아래와 같이 구현하였지만 코드가 난잡하고 중복되는 것이 많아 알아보기 힘들었다. 중복을 없애고, 안되는 것을 먼저 없애는 방식으로 코드를 개선했다.

처음 통과 코드

from collections import deque

my = [1,-1,0,0]
mx = [0,0,1,-1]

def solution(board):
    N = len(board)
    visited = [[[0] * 2 for _ in range(N)] for _ in range(N)]
    visited[0][0][0] = 1
    visited[0][1][0] = 1
    q = deque([(0,0,0,1,0,0)])
    while q:
        y1,x1,y2,x2,cnt, direc = q.popleft()
        if (y1, x1) == (N - 1, N - 1) or (y2, x2) == (N - 1, N - 1):
            return cnt
        for i in range(4):
            dy1,dx1,dy2,dx2 = y1 + my[i], x1 + mx[i], y2 + my[i], x2 + mx[i]
            if 0 <= dy1 < N and 0 <= dx1 < N and 0 <= dy2 < N and 0 <= dx2 < N:
                if not board[dy1][dx1] and not board[dy2][dx2]:
                    if not (visited[dy1][dx1][direc] and visited[dy2][dx2][direc]):
                        visited[dy1][dx1][direc] = 1
                        visited[dy2][dx2][direc] = 1
                        q.append((dy1,dx1,dy2,dx2,cnt+1,direc))
        if direc == 0:
            if y2 -1 >= 0 and y1 -1 >= 0:
                if not board[y2-1][x2] and not board[y1-1][x1] and not visited[y1-1][x1][1]:
                    visited[y1 - 1][x1][1] = 1
                    visited[y1][x1][1] = 1
                    q.append((y1,x1,y1-1,x1,cnt+1,1))
                if not board[y1-1][x1] and not board[y2-1][x2] and not visited[y2-1][x2][1]:
                    visited[y2 - 1][x2][1] = 1
                    visited[y2][x2][1] = 1
                    q.append((y2-1,x2,y2,x2,cnt+1,1))
            if y2 +1 < N and y1 + 1 < N:
                if not board[y2+1][x2] and not board[y1+1][x1] and not visited[y1+1][x1][1]:
                    visited[y1+ 1][x1][1] = 1
                    visited[y1][x1][1] = 1
                    q.append((y1,x1,y1+1,x1,cnt+1,1))
                if not board[y1+1][x1] and not board[y2+1][x2] and not visited[y2+1][x2][1]:
                    visited[y2 + 1][x2][1] = 1
                    visited[y2][x2][1] = 1
                    q.append((y2,x2,y2+1,x2, cnt+1,1))
        if direc == 1:
            if x1 -1 >= 0 and x2 -1 >= 0:
                if not board[y2][x2-1] and not board[y1][x1-1] and not visited[y1][x1-1][0]:
                    visited[y1][x1-1][0] = 1
                    visited[y1][x1][0] = 1
                    q.append((y1,x1-1,y1,x1,cnt+1,0))
                if not board[y1][x1-1] and not board[y2][x2-1] and not visited[y2][x2-1][0]:
                    visited[y2][x2-1][0] = 1
                    visited[y2][x2][0] = 1
                    q.append((y2,x2-1,y2,x2,cnt+1,0))
            if x1 + 1 < N  and x2+1 < N:
                if not board[y2][x2+1] and not board[y1][x1+1] and not visited[y1][x1+1][0]:
                    visited[y1][x1+1][0] = 1
                    visited[y1][x1][0] = 1
                    q.append((y1,x1,y1,x1+1,cnt+1,0))
                if not board[y1][x1+1] and not board[y2][x2+1] and not visited[y2][x2+1][0]:
                    visited[y2][x2+1][0] = 1
                    visited[y2][x2][0] = 1
                    q.append((y2,x2,y2,x2+1,cnt+1,0))
    return -1