[프로그래머스] Lv3. 블록 이동하기 (2020 카카오 공채)

🔗

풀이

기존에 한 칸씩 하던 그래프 탐색을 두 칸씩 해야 하는 문제.

최단거리를 구해야 하기 때문에 BFS를 사용했다. 모든 경우는 (1) 상하좌우 이동, (2) 시계, 반시계 방향의 90도 회전이 가능하다. 회전의 경우 두 칸이기 때문에 각각의 칸을 기준으로 잡고 다른 칸을 회전시킬 수 있으므로 총 4개의 경우가 존재한다. 각 경우에 대해서 (1) 배열을 벗어나는 경우 (2) 이미 방문한 칸인 경우 (3) 회전 도중에 벽이 존재하는 경우를 제외하면 된다.

def solution(board): 
    # 2칸에 대해 왼쪽 위에 있는 칸을 먼저 저장
    # 방문처리를 하고 큐에 추가
    def save_key(x1, y1, x2, y2, step):
        if (x1, y1) < (x2, y2):
            key = x1, y1, x2, y2
        else:
            key = x2, y2, x1, y1
        visited[key] = step
        Q.append(key)
    
    # 방문 가능한 칸인지 확인
    def is_valid(x1, y1, x2, y2):
        # 범위를 벗어나는 경우
        if not(-1<x1<n and -1<y1<n and -1<x2<n and -1<y2<n):
            return False
        # 한쪽이 벽인 경우
        if board[x1][y1] or board[x2][y2]:
            return False
        # 이미 방문한 곳인 경우
        if (x1, y1, x2, y2) in visited or (x2, y2, x1, y1) in visited:
            return False
        return True

    n = len(board)
    Q, visited = deque(), defaultdict(int)
    Q.append((0, 0, 0, 1))
    visited[(0, 0, 0, 1)] = 1
    while Q:
        x1, y1, x2, y2 = Q.popleft()
        step = visited[(x1, y1, x2, y2)]
        if (n-1, n-1) in ((x1, y1), (x2, y2)):
            print(visited)
            return step-1
        
        step += 1
        # 가로세로 모두 상하좌우 이동 가능
        if is_valid(x1-1, y1, x2-1, y2):
            save_key(x1-1, y1, x2-1, y2, step)
        if is_valid(x1+1, y1, x2+1, y2):
            save_key(x1+1, y1, x2+1, y2, step)
        if is_valid(x1, y1-1, x2, y2-1):
            save_key(x1, y1-1, x2, y2-1, step)
        if is_valid(x1, y1+1, x2, y2+1):
            save_key(x1, y1+1, x2, y2+1, step)
        if x1 == x2: # 가로일 때 각각의 기준점에 대해 시계/반시계 회전
            if x1>0:
                if not board[x1-1][y2] and is_valid(x1-1, y1, x1, y1):
                    save_key(x1, y1, x1-1, y1, step)
                if not board[x2-1][y1] and is_valid(x2-1, y2, x2, y2):
                    save_key(x2-1, y2, x2, y2, step)
            if x1<n-1:
                if not board[x1+1][y2] and is_valid(x1, y1, x1+1, y1):
                    save_key(x1, y1, x1+1, y1, step)
                if not board[x2+1][y1] and is_valid(x2, y2, x2+1, y2):
                    save_key(x2, y2, x2+1, y2, step)
        else:
            if y1>0:
                if not board[x2][y1-1] and is_valid(x1, y1, x1, y1-1):
                    save_key(x1, y1, x1, y1-1, step)
                if not board[x1][y1-1] and is_valid(x2, y2, x2, y1-1):
                    save_key(x2, y2, x2, y1-1, step)
            if y1<n-1:
                if not board[x2][y1+1] and is_valid(x1, y1, x1, y1+1):
                    save_key(x1, y1, x1, y1+1, step)
                if not board[x1][y1+1] and is_valid(x2, y2, x2, y1+1):
                    save_key(x2, y2, x2, y1+1, step)
       
from collections import deque, defaultdict