처음에 계속 메모리 초과가 났는데 다시 생각해보면 회전 로직에서 시간 초과가 났던 것 같다.
회전 시 통나무의 중심축을 제외한 두 좌표에 대해 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()
'Problem Solving > 백준' 카테고리의 다른 글
27440 : 1로 만들기 3 Python (0) | 2024.05.23 |
---|---|
31791 : 바이러스 공격 Python (0) | 2024.05.09 |
14728 : 벼락치기 Python (0) | 2024.04.28 |
14939 : 불 끄기 Python (0) | 2024.04.19 |