1938 : 통나무 옮기기 Python

1938 : 통나무 옮기기

 

처음에 계속 메모리 초과가 났는데 다시 생각해보면 회전 로직에서 시간 초과가 났던 것 같다.
회전 시 통나무의 중심축을 제외한 두 좌표에 대해 y값과 x값이 바뀐다고 생각을 했었다.. 그렇게 생각하니 아래와 같이 정렬을 해줘야 했고 불필요한 리스트를와 패킹하기 위해 또다른 리스트를 만들었다. 아마 이부분에서 시간 초과가 난게 아닌가 싶다.

# 따로 정렬이 필요
if can_turn(y2, x2):
    # 변형
    n_pos = sorted([(x1, y1), (y2, x2), (x3, y3)])
    n_pos = tuple([*n_pos[0], *n_pos[1], *n_pos[2]])
    if n_pos in v:
        continue
        v.add(n_pos)
        q.append(n_pos)

아무튼 메모리 초과문제를 해결하지 못했고 아래 글을 통해 회전 로직에 대한 아이디어를 얻고 해결했다.

[BOJ] 1938. 통나무 옮기기(Python) / BFS

핵심적인 아이디어는 통나무의 가로/세로 방향을 상태로 저장하는 것이다. 통나무의 회전 로직은 가로와 세로 방향에 따라 고정되는 값이 바뀌게 된다.

 

가로 -> 세로 회전일 경우

위와 같이 가로에서 세로 방향으로 회전을 할 경우 중심축을 pos라고 했을 때, 회전한 통나무의 x좌표는 pos의 x좌표로 고정된다. 그 뒤, pos의 y좌표를 ny라고 했을 때, ny - 1, ny, ny + 1의 좌표를 갖게 된다.

 

세로 -> 가로 회전일 경우

가로로 회전할 경우 중심축을 pos라고 했을 때, 회전한 통나무의 y좌표는 pos의 y좌표로 고정된다. 그 뒤, pos의 x좌표를 nx라고 했을 때, nx - 1, nx, nx + 1의 좌표를 갖게 된다.

 

따라서 현재 상태를 저장할 status와 방향에 맞게 회전시켜 주면 된다.

전체 코드

import sys
from collections import deque

# print = sys.stdout.write
input = sys.stdin.readline
# 반드시 아래 두 라인 주석 처리 후 제출
# f = open("input.txt", "rt")
# input = f.readline
# 반드시 위 두 라인 주석 처리 후 제출

dy, dx = (-1, 1, 0, 0, -1, -1, 1, 1), (0, 0, -1, 1, -1, 1, 1, -1)
END = ("E", "E", "E")
N = int(input().rstrip())
board, start = [], []

for i in range(N):
    row = list(input().rstrip())
    for j in range(N):
        if row[j] == "B":
            start.extend((i, j))
    board.append(row)
if start[0] == start[2] == start[4]:
    start.append(0)  # 가로로 한 줄 -> y값 고정
else:
    start.append(1)  # 세로로 한 줄 -> x값 고정

start = tuple(start)


def can_turn(y, x):
    for i in range(8):
        ny, nx = dy[i] + y, dx[i] + x
        # 물리적으로 가능한지만 확인
        if ny >= N or nx >= N or ny < 0 or nx < 0 or board[ny][nx] == "1":
            return False

    return True


def can_move(y, x):
    for i in range(3):
        ny, nx = y[i], x[i]
        if ny >= N or nx >= N or ny < 0 or nx < 0 or board[ny][nx] == "1":
            return False

    return True


def BFS():
    q = deque([start])
    t = 0
    v = set()
    v.add(start)
    while q:
        q_size = len(q)
        for _ in range(q_size):
            y1, x1, y2, x2, y3, x3, status = q.popleft()

            if (board[y1][x1], board[y2][x2], board[y3][x3]) == END:
                return t

            for i in range(4):
                ny, nx = (dy[i] + y1, dy[i] + y2, dy[i] + y3), (
                    dx[i] + x1,
                    dx[i] + x2,
                    dx[i] + x3,
                )
                if not can_move(ny, nx):
                    continue

                next = (ny[0], nx[0], ny[1], nx[1], ny[2], nx[2], status)

                if next in v:
                    continue

                q.append(next)
                v.add(next)

            if can_turn(y2, x2):
                nstatus = (status + 1) % 2
                # 가로에서 세로로 변경
                if nstatus == 1:
                    next = (y2 - 1, x2, y2, x2, y2 + 1, x2, nstatus)

                # 세로로 변경
                else:
                    next = (y2, x2 - 1, y2, x2, y2, x2 + 1, nstatus)

                if next in v:
                    continue
                q.append(next)
                v.add(next)

        t += 1
    return 0


def main():
    print(BFS())


if __name__ == "__main__":
    main()