Programmers. 블록 이동하기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 블록 이동하기

문제 풀이

괴랄한 bfs라 생각했는데 조금만 더 직관이 들어갔으면 해결할 수 있었을지도 모르겠다. 여전히 시뮬레이션 문제는 너무나 어렵다.

상하좌우는 쉬운데 회전 처리가 감이 안잡힌다. 그러나 회전 경로에 칸이 없어야 함은 주어졌으므로 해당 방향으로 평행 이동이 가능하다면 회전 또한 가능함을 보여준다. 그리고 시간 복잡도를 줄이기 위해 양 모터의 좌표를 set에 담아 동일 포지션에서의 재탐색을 막도록 한다. 그리고 회전 시 맵 바깥으로의 이동을 방지하기 위해 전체 맵을 1로 감싸면 연산이 편하다.

• 주어진 좌표에서 움직일 수 있는 좌표들을 담은 배열을 반환하는 함수 정의
  • 상하좌우 및 수평, 수직 상태에서 상하좌우로 움직일 수 있다면 회전가능
• 맵 전체를 외벽으로 감싸서 새로운 지도 완성
• 큐에 초기 모터 좌표 입력, 모터가 2개이므로 좌표도 2개이고 비용은 0부터 시작
• 큐가 없어질 때까지 popleft하여 움직일 수 있는 좌표가 있는지 탐색

python 코드

from collections import deque
def solution(board):
    def move(p1, p2):
        pos = []
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dr, dc in dirs:
            np1 = (p1[0] + dr, p1[1] + dc)
            np2 = (p2[0] + dr, p2[1] + dc)
            if grid[np1[0]][np1[1]] == 0 and grid[np2[0]][np2[1]] == 0:
                pos.append((np1, np2))
        if p1[0] == p2[0]:
            for i in [1, -1]:
                if grid[p1[0] + i][p1[1]] == 0 and grid[p2[0] + i][p2[1]] == 0:
                    pos.append((p1, (p2[0] + i, p1[1])))
                    pos.append(((p1[0] + i, p2[1]), p2))
        else:
            for i in [1, -1]:
                if grid[p1[0]][p1[1] - i] == 0 and grid[p2[0]][p2[1] - i] == 0:
                    pos.append((p1, (p1[0], p2[1] - i)))
                    pos.append(((p2[0], p1[1] - i), p2))
        return pos
    N = len(board)
    grid = [[1 for _ in range(N + 2)] for _ in range(N + 2)]
    for r in range(N):
        for c in range(N):
            grid[r + 1][c + 1] = board[r][c]

    q = deque([((1,1), (1,2), 0)])
    confirm = set()
    confirm.add(((1,1), (1,2)))
    answer = 0
    while q:
        p1, p2, result = q.popleft()
        if p1 == (N,N) or p2 == (N,N):
            return result
        for k in move(p1, p2):
            if k not in confirm:
                q.append((k[0], k[1], result + 1))
                confirm.add(k)