[백준`G2] 1938 - 통나무 옮기기 (Python)

문제 설명

https://www.acmicpc.net/problem/1938

 

성능 요약

메모리: 34216 KB, 시간: 72 ms

 

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현

 

제출 일자

2024년 4월 23일 00:47:02

 

문제 설명

가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 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도 회전시킨다.

예를 들면, 다음과 같다. (초기상태로부터의 이동)

초기상태	상(U)	하(D)	좌(L)	우(R)	회전(T)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B B B 0 0 0 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 0 0 1 0 0

이와 같은 방식으로 이동시킬 때에 그 움직일 위치에 다른 나무, 즉 1이 없어야만 움직일 수 있다. 그리고 움직임은 위의 그림과 같이 한 번에 한 칸씩만 움직인다. 단 움직이는 통나무는 어떤 경우이든지 중간단계에서 한 행이나 한 열에만 놓일 수 있다. 예를 들면 아래 그림에서 a와 같은 단계는 불가능하다. 그리고 회전의 경우에서는 반드시 중심점을 중심으로 90도 회전을 해야 한다. (항상 통나무의 길이가 3이므로 중심점이 있음)

그리고 이런 회전(Turn)이 가능하기 위해서는 그 통나무를 둘러싸고 있는 3*3 정사각형의 구역에 단 한 그루의 나무도 없어야만 한다. 즉, 아래그림 b, d와 같이 ?로 표시된 지역에 다른 나무, 즉 1이 없어야만 회전시킬 수 있다. 따라서 c와 같은 경우에, 통나무는 왼쪽 아직 벌채되지 않은 나무 때문에 회전시킬 수 없다.

a	b	c	d
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 B 0 0 0 0 B 0 0 0 0 B 0 0 0 0 0 0 0 1 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? ? ? 0 0 0 B B B 0 0 0 ? ? ? 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 B 0 0 0 0 0 B 0 0 0 0 0 B 0 0 0 0 0 0 0 0	0 0 0 0 0 0 0 0 0 0 0 0 0 0 ? B ? 0 0 0 ? B ? 0 0 0 ? B ? 0 0 0 0 0 0 0

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

 

입력

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

 

출력

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

---

문제 풀이

bfs를 사용해서 풀었다.

통나무는 길이가 무조건 3이기 때문에, 중심점을 기준으로 위치를 계산했다.

 

큐에 중심점의 좌표와 세로인지 가로인지 확인하는 변수, 횟수를 넣어 pop해가며 구했다.

중심점이 범위를 벗어나거나 4개의 꼭짓점에 위치하거나, 위치가 1이면 통나무가 위치할 수 없는 자리이기 때문에 넘겨주었다.

 

x, y에서 동작할 수 있는 경우의 수는 위, 아래, 왼쪽, 오른쪽, 회전 이렇게 5가지가 있다.

먼저 반복문으로 위, 아래, 왼쪽, 오른쪽을 체크하며 

세로 방향일 때 범위 안쪽이면서 방문하지 않았고, 위칸, 아래칸에 1이 없으면 queue에 추가해주었고,

가로 방향일 때 범위 안쪽이면서 방문하지 않았고, 왼쪽 칸, 오른쪽 칸에 1이 없으면 queue에 추가해주었다.

방문 처리는 같은 좌표라도 통나무의 방향(가로, 세로)에 따라 다른 경우로 취급되기 때문에 나누어서 처리를 해주었다.

 

회전할 때도 같은 방식으로 체크해주었다.

중심점을 기준으로 주변 9칸을 체크해야 하는데, 통나무가 세로든 가로든 상관없이 꼭짓점은 무조건 지나가기 때문에

9칸의 꼭짓점에 1이 있는지 체크한 후 가로인지 세로인지 방향을 체크하여 방문 처리를 해주었다.

 

from collections import deque

N = int(input())
area = [list(input()) for _ in range(N)]
queue = deque()
visited_col = [[False] * N for _ in range(N)]
visited_row = [[False] * N for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(end_x, end_y, end_c):
    while queue:
        x, y, c, ct = queue.popleft()
        if x == end_x and y == end_y and c == end_c:
            print(ct)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > N - 1 or ny < 0 or ny > N - 1:
                continue
            # 각 꼭짓점일 때
            if ((nx == 0 and ny == 0) or (nx == 0 and ny == N - 1)
                    or (nx == N - 1 and ny == 0) or (nx == N - 1 and ny == N - 1)):
                continue
            if area[nx][ny] == '1':
                continue
			
            # 세로 방향
            if c and 0 < nx < N - 1 and not visited_col[nx][ny]:
            	# 중심점 기준 위쪽, 아래쪽에 1이 있는지 확인
                if area[nx - 1][ny] != '1' and area[nx + 1][ny] != '1':
                    queue.append((nx, ny, 1, ct + 1))
                    visited_col[nx][ny] = True
            # 가로 방향
            if not c and 0 < ny < N - 1 and not visited_row[nx][ny]:
            	# 중심점 기준으로 왼쪽, 오른쪽에 1이 있는지 확인
                if area[nx][ny - 1] != '1' and area[nx][ny + 1] != '1':
                    queue.append((nx, ny, 0, ct + 1))
                    visited_row[nx][ny] = True
		
        # 회전
        if 0 < x < N - 1 and 0 < y < N - 1:
        	# 회전하는 주변에 1이 없을 때 queue에 추가
            if (area[x - 1][y - 1] != '1' and area[x - 1][y + 1] != '1'
                    and area[x + 1][y - 1] != '1' and area[x + 1][y + 1] != '1'):
                if c and not visited_row[x][y]:
                    if area[x][y - 1] != '1' and area[x][y + 1] != '1':
                        queue.append((x, y, 0, ct + 1))
                        visited_row[x][y] = True
                elif not c and not visited_col[x][y]:
                    if area[x - 1][y] != '1' and area[x + 1][y] != '1':
                        queue.append((x, y, 1, ct + 1))
                        visited_col[x][y] = True
    print(0)


b, e = [], []
for i in range(N):
    for j in range(N):
        if area[i][j] == 'B':
            b.append((i, j))
        elif area[i][j] == 'E':
            e.append((i, j))

bx, by = b[1][0], b[1][1]
ex, ey = e[1][0], e[1][1]

if b[0][0] == bx:
    queue.append((bx, by, 0, 0))
    visited_row[bx][by] = True
else:
    queue.append((bx, by, 1, 0))
    visited_col[bx][by] = True

if e[0][0] == ex:
    bfs(ex, ey, 0)
else:
    bfs(ex, ey, 1)