[백준] 1938 : 통나무 옮기기 - Python

문제

길이 3인 통나무 BBB를 회전 or 상하좌우 이동시켜서 EEE(도착점)으로 옮기는 문제.
이동할 곳에 1이 없어야만 움직일 수 있다.
회전 시에는 통나무가 존재하는 위치 기준 3*3 정사각형에 1이 없어야만 이동할 수 있다.

보드에는 0,1,B,E 값을 가진다.

구하고자 : 도착지 가는데 최소 동작 횟수 -> 다익스트라로 생각 가능

통나무의 위치 표현 : 중심점의 좌표로 표현, 통나무의 방향은 가로 방향, 세로방향 두 가지 존재.
-> (x,y,0) : 통나무의 중심점 x,y이고 가로 방향
-> (x,y,1) : 통나무 중심점 x,y이고 세로방향

이동 및 회전 연산 :
상하좌우 : 통나무 중심점을 기준으로 상하좌우 한칸씩 이동.

• 이동할 위치에 1 없어야만 이동가능
• 이동 후 통나무 방향 유지

회전연산 : 통나무 중심점 기준 90도 회전

• 회전할 때 통나무 둘러싸는 3*3 정사각형 1 없는지 확인 후 없으면 회전, 회전 후 통나무 방향 변경

내 코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

# nxn 보드 0 빈칸, 1 벽(잘리지 않은 나무)
# 길이3 통나무 BBB 상하좌우, 회전을 통해 도착점으로 가야함
# 이동할 곳에 1이 없어야만 이동 가능
# 회전시에 통나무 포함되어 있는 3*3제외 1 없어야만 회전 가능
# 구하고자 : 최소의 움직임으로 이동 -> 다익스트라
n = int(input())
g = [list(map(str, input())) for _ in range(n)]

startX,startY = 0,0
endX,endY = 0,0
direction = 0 # 시작 방향 0 : 가로, 1 : 세로
end_dir = 0
def isIn(x,y):
    if 0<=x<n and 0<=y<n:
        return True
    return False
flag = False
for i in range(n):
    for j in range(n):
        if g[i][j] == "B": # 시작점 시작
            if isIn(i,j+1) and g[i][j+1] == "B": # 가로로 있는 상태
                startX,startY,direction = i,j+1,0
                g[i][j],g[i][j+1],g[i][j+2] = "0","0","0" # 시작점 모두 빈칸으로 만들기
            elif isIn(i+1,j) and g[i+1][j] == "B":
                startX,startY,direction =i+1,j,1
                g[i][j],g[i+1][j],g[i+2][j] = "0","0","0" # 시작점 모두 빈칸으로
            flag = True
            break
    if flag: break
flag = False
for i in range(n):
    for j in range(n):
        if g[i][j] == "E":
            if isIn(i,j+1) and g[i][j+1] == "E":
                endX,endY,end_dir = i,j+1,0
            elif isIn(i+1,j) and g[i+1][j]:
                endX,endY,end_dir =i+1,j,1
            flag = True
            break
    if flag: break
# print(f" 시작점 : {startX,startY} 도착점 : {endX,endY}")
# 시작점, 도착점 세팅끝
# (x,y)에 도착했을 때 그 상태가 어떤 상황에서 도착한지 알 수 없으므로!!
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y,dir): # 현재 중심 위치(x,y) 그리고 방향이 dir일때 존재 가능 ?
    if dir == 0: # 가로로 존재
        if not (0<=x<n and 1<=y<n-1):
            return False
        for i in (y-1,y,y+1):
            if g[x][i] == "1": # 벽 -> 이동 불가
                return False
    else: # 세로로 존재
        if not (1<=x<n-1 and 0<=y<n):
            return False
        for i in (x-1,x,x+1):
            if g[i][y] == "1":
                return False
    return True
def can_turn(x,y):
    cnt = 0
    if not (1 <= x < n - 1 and 1 <= y < n - 1): return False
    for i in (x-1,x,x+1):
        for j in (y-1,y,y+1):
            if g[i][j] == "1": return False
    return True
# def turn(x,y,dir):
#     # 중심좌표 (x,y) 기준 dir로회전 진행
#     for i in (x-1,x,x+1):
#         for j in (y-1,y,y+1):
#             g[i][j] = "0" # 일단 모두 초기화 후에
#     if dir == 0: # 가로로 진행
#         for i in (y-1,y,y+1):
#             g[x][i] = "1"
#     else:
#         for i in (x-1,x,x+1):
#             g[i][y] = "1"


def BFS(startX,startY,direction):
    global res
    dq = deque()
    dq.append((startX,startY,direction,0)) # 시작 위치, 시작 위치의 방향, 현재 경로횟수
    dis[startX][startY][direction] = 0 # 시작 위치에서의 시작방향. 값 0

    while dq:
        x,y,dir, cnt = dq.popleft() # 현재 경로의 현재 위치(중심좌표), 방향, 현재까지 이동 횟수
        # print(f"현재 확인할 경로 : 현재 중심 위치 : {(x,y)}, 현재 방향 : {dir}, 현재 경로까지의 이동 횟수 : {cnt}")
        if (x,y,dir) == (endX,endY,end_dir):
            # print("도착")
            res = min(res,cnt)
            continue
        for i in range(4): # 상하좌우 먼저 판단.
            nx = x + dx[i]
            ny = y + dy[i]
            if isInner(nx,ny,dir): # 해당 좌표 이동 가능
                if cnt + 1 < dis[nx][ny][dir]: # 현재 통나무 방향(가로or세로)로 갔을 때의 최단거리보다 작은 경우
                    # print(f"{(nx,ny)} 도착 가능 거리 갱신 : {cnt+1}, 현재 방향 : {dir}")
                    dis[nx][ny][dir] = cnt + 1
                    dq.append((nx,ny,dir,cnt+1))
        # 회전
        if dir == 0: # 현재 가로로 존재 -> 세로로 회전
            if can_turn(x,y) and cnt + 1 < dis[x][y][1]: # 현재 중심좌표에서 회전 가능
                # print(f"{(x, y)} 도착 가능 거리 갱신 : {cnt + 1}, 현재 방향 : {1}")
                dis[x][y][1] = cnt + 1
                dq.append((x,y,1,cnt+1))
        else: # 현재 방향 1 -> 세로 -> 가로로 회전
            if can_turn(x,y) and cnt + 1 < dis[x][y][0]:
                # print(f"{(x,y)} 도착 가능, 거리 갱신 : {cnt+1}, 현재 방향 : {0 }")
                dis[x][y][0] = cnt + 1
                dq.append((x,y,0,cnt+1))

INF = int(1e9)
dis = [[[INF] * 2 for _ in range(n)] for _ in range(n)] # 가로,세로 상태가 2개이기에 3차원 배열로 해야한다.
res = int(1e9)
BFS(startX,startY,direction)
if res == INF:
    print(0)
else:
    print(res)
  

코멘트

기존의 다익스트라 문제와 생각은 같지만.. 위치가 3칸을 차지하는 문제. 푸는데 생각을 많이 했어야 했다.

통나무를 상하좌우 이동시키거나 회전시켜 목적지로 옮기는 최소 움직임 횟수 구하기

→ 다익스트라로 접근

통나무의 현재 위치와 방향에 따라 다음 상태가 결정된다. → 모든 경로를 탐색해야 한다.

가장 중요한 것이 같은 위치에 도달하더라도 통나무의 방향에 따라 상태가 다르므로, 3차원 dis 배열을 사용하여 각 위치와 방향에 대한 최단거리를 저장했어야 헀다.

• 3차원 만드는 이유 : 통나무는 같은 위치에 있더라도, 가로 방향과 세로 방향. 두 가지 상태를 가질 수 있다. 따라서 단순히 2차원 배열로는 방문 여부를 표현할 수 없다. 예를 들어, (3,3) 위치에 가로방향으로 있을 때와 세로 방향으로 있을 때는 서로 다른 상태로 취급해야 한다. 만약 2차원 배열로 최단거리를 처리한다면, (3,3) 위치를 방문했다고 표시했을 때 가로 방향인지 세로방향인지 구분할 수 없게 된다.
• 이를 해결하고자 3차원 배열 사용. → 3차원 배열의 첫번째 두번쨰 차원은 통나무의 위치를 나타내고, 세번째 차원은 통나무의 방향을 나타낸다.
• 이렇게 3차원 배열을 사용하면 통나무의 위치와 방향을 모두 고려하여 최단거리를 갱신할 수 있게 된다.

이동할 때는 나무 존재(벽:1)없는 빈칸(0)으로만 이동할 수 있으며 회전할 때는 통나무를 둘러싸는 3*3 영역에 벽이 없어야 한다.

주의했어야 했던게, 시작점과 도착점을 찾을 때 통나무가 가로방향인지, 세로방향인지 모두 고려해야 한다.

말이되고픈원숭이, 벽 부수고 이동하기2 문제처럼 아이디어는 같지만, 현재 위치를 3칸이 차지해서 좀 복잡하게 구현하려고 했다.. 계속 움직이면서 1을 채우고 0을 지운다던지.. 그럴 필요없었는데,,

벽 부수고 이동하기2 문제에서도 역시 벽을 부순 횟수에 따라 상태가 달라지기 때문에 2차원 배열로는 부족하고 3차원 배열을 사용하여 (x,y좌표, 벽을 부순 횟수)를 저장.

말이 되고픈 원숭이 문제에서는 각 위치마다 원숭이의 상태(말 or 원숭이)에 따라 이동 방식이 달라지기 때문에 2차원이 아닌 3차원 배열을 사용하여 (x좌표, y좌표,원숭이 상태 저장)

통나무 옮기기 문제에서도 마찬가지로, 각 위치마다 통나무의 방향(가로or세로)에 따라 상태가 달라지기 때문에 3차원 배열을 사용해야 한다. 3차원 배열의 각 차원은 다음과 같은 의미 가짐

• 1차원: 통나무의 중심 좌표 x
• 2차원: 통나무의 중심 좌표 y
• 3차원: 통나무의 방향 (0: 가로, 1: 세로)

이렇게 3차원 배열을 사용하면 각 위치에서 통나무의 방향에 따른 최단 거리를 저장할 수 있습니다. 예를 들어, dis[i][j][0]은 통나무의 중심이 (i, j)이고 가로 방향일 때의 최단 거리를, dis[i][j][1]은 통나무의 중심이 (i, j)이고 세로 방향일 때의 최단 거리를 나타냅니다.

이처럼 문제에서 고려해야 할 상태가 여러 가지인 경우, 다차원 배열을 사용하여 각 상태에 대한 정보를 저장할 수 있습니다. 통나무 옮기기 문제에서는 위치와 방향을 함께 고려해야 하므로 3차원 배열을 사용하는 것이 적절한 방법이었습니다.