[ BOJ ] 1938 : 통나무 옮기기 ( GOLD 2 ) / Python

문제

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자.

B 0 0 1 1
B 0 0 0 0
B 0 0 0 0
1 1 0 0 0
E E E 0 0

위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 3이며 B의 개수와 E의 개수는 같다. 통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다.

- 코드의미

U	통나무를 위로 한 칸 옮긴다.
D	통나무를 아래로 한 칸 옮긴다.
L	통나무를 왼쪽으로 한 칸 옮긴다.
R	통나무를 오른쪽으로 한 칸 옮긴다.
T	중심점을 중심으로 90도 회전시킨다.

문제는 통나무를 5개의 기본동작(U, D, L, R, T)만을 사용하여 처음위치(BBB)에서 최종위치(EEE)로 옮기는 프로그램을 작성하는 것이다. 단, 최소 횟수의 단위 동작을 사용해야 한다.

입력

첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.

출력

첫째 줄에 최소 동작 횟수를 출력한다. 이동이 불가능하면 0만을 출력한다.

풀이 과정

BFS를 사용하면서 방향에 따른 방문 처리를 추가했다. 중심점을 이용한 이동으로 탐색을 진행했다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
maps = [list(input()) for _ in range(n)]

start_wood = []
end_wood = []
for i in range(n):
    for j in range(n):
        if maps[i][j] == 'B': start_wood.append([i, j])
        if maps[i][j] == 'E': end_wood.append([i, j])

start_wood_mid = start_wood[1]
end_wood_mid = end_wood[1]

# 0 : Sero, 1 : Garo
start_dir = 0 if start_wood[0][1] == start_wood[1][1] == start_wood[2][1] else 1
end_dir = 0 if end_wood[0][1] == end_wood[1][1] == end_wood[2][1] else 1

q = deque()
q.append([start_wood_mid[0], start_wood_mid[1], start_dir])

visit = [[[0 for k in range(2)] for j in range(n)] for i in range(n)]
visit[start_wood_mid[0]][start_wood_mid[1]][start_dir] = 1

done = 0
time = 0
# Up, Down, Left, Right
row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

dirs = [[[-1, 0], [1, 0]], [[0, -1], [0, 1]]]
while q:
    size = len(q)

    for s in range(size):
        y = q[0][0]; x = q[0][1]; dir = q[0][2]
        q.popleft()

        if y == end_wood_mid[0] and x == end_wood_mid[1] and dir == end_dir:
            done = 1
            break

        pieces = [[y + dirs[dir][0][0], x + dirs[dir][0][1]], [y, x], [y + dirs[dir][1][0], x + dirs[dir][1][1]]]

        for d in range(4):
            cant = 0
            for p in range(3):
                if not (0 <= pieces[p][0] + row[d] < n and 0 <= pieces[p][1] + col[d] < n and maps[pieces[p][0] + row[d]][pieces[p][1] + col[d]] != '1'): cant = 1
            
            if cant == 0 and visit[y + row[d]][x + col[d]][dir] == 0:
                visit[y + row[d]][x + col[d]][dir] = 1
                q.append([y + row[d], x + col[d], dir])
        
        if dir == 0:
            cant = 0
            for p in range(3):
                if not (0 <= pieces[p][1] + col[2] < n and 0 <= pieces[p][1] + col[3] < n and maps[pieces[p][0]][pieces[p][1] + col[2]] != '1' and maps[pieces[p][0]][pieces[p][1] + col[3]] != '1'): cant = 1

            if cant == 0 and visit[y][x][1] == 0:
                visit[y][x][1] = 1
                q.append([y, x, 1])
        else:
            cant = 0
            for p in range(3):
                if not (0 <= pieces[p][0] + row[0] < n and 0 <= pieces[p][0] + row[1] < n and maps[pieces[p][0] + row[0]][pieces[p][1]] != '1' and maps[pieces[p][0] + row[1]][pieces[p][1]] != '1'): cant = 1

            if cant == 0 and visit[y][x][0] == 0:
                visit[y][x][0] = 1                
                q.append([y, x, 0])
        
    if done == 1: break
    time += 1

print(time if done == 1 else 0)