간단한 bfs 문제라고 생각했는데, 복병이 숨어 있었다.
from collections import deque
K = int(input())
h_dx = [1, 2, -1, -2, 1, 2, -1, -2]
h_dy = [2, 1, -2, -1, -2, -1, 2, 1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 0, 0에서 시작
q = deque([(0, 0, 0, 0)])
# (H-1, W-1) 까지 가야 함
W, H = map(int, input().split())
# 체스판 만들기
visited = [[0 for _ in range(W)] for _ in range(H)]
visited[0][0] = 1
board = []
for i in range(H):
board.append(list(map(int, input().split())))
def move_monkey():
while len(q):
cx, cy, move, h_move = q.popleft()
# 한 번 움직이기
move += 1
# 아직 말처럼 K번 안 움직였으면 말처럼 원숭이 움직이기
if h_move < K:
for i in range(8):
nx, ny = cx + h_dx[i], cy + h_dy[i]
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == 0 and board[nx][ny] != 1:
if nx == H - 1 and ny == W - 1:
return move
q.append((nx, ny, move, h_move + 1))
visited[cx][cy] = 1
# 원숭이 기본 움직이기
for i in range(4):
nx, ny = cx + dx[i], cy + dy[i]
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == 0 and board[nx][ny] != 1:
if nx == H - 1 and ny == W - 1:
return move
q.append((nx, ny, move, h_move))
visited[cx][cy] = 1
return -1
print(move_monkey())
계속 시간초과가 나서, 만약 이동했을 때 조건에 맞아서 큐에 들어가야 하는 위치이면 이동 시키기 전에 바로 visited 처리를 해줬다.
근데, 이렇게 처리를 해줬는데도 시간초과가 났다..😢
from collections import deque
K = int(input())
h_dx = [1, 2, -1, -2, 1, 2, -1, -2]
h_dy = [2, 1, -2, -1, -2, -1, 2, 1]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 0, 0에서 시작
q = deque([(0, 0, 0, 0)])
# (H-1, W-1) 까지 가야 함
W, H = map(int, input().split())
# 체스판 만들기
board = []
for i in range(H):
board.append(list(map(int, input().split())))
# 방문 처리
visited = [[[0 for _ in range(K + 1)] for _ in range(W)] for _ in range(H)]
visited[0][0][0] = 1
def check(nx, ny, h_move):
if 0 <= nx < H and 0 <= ny < W:
if visited[nx][ny][h_move] == 0 and board[nx][ny] != 1:
return True
return False
def move_monkey():
while len(q):
cx, cy, move, h_move = q.popleft()
if cx == H - 1 and cy == W - 1:
return move
# 한 번 움직이기
move += 1
# 아직 말처럼 K번 안 움직였으면 말처럼 원숭이 움직이기
if h_move < K:
for i in range(8):
nx, ny = cx + h_dx[i], cy + h_dy[i]
if check(nx, ny, h_move + 1):
q.append((nx, ny, move, h_move + 1))
visited[nx][ny][h_move + 1] = 1
# 원숭이 기본 움직이기
for i in range(4):
nx, ny = cx + dx[i], cy + dy[i]
if check(nx, ny, h_move):
q.append((nx, ny, move, h_move))
visited[nx][ny][h_move] = 1
return -1
print(move_monkey())
말의 움직임으로 이동을 했는지, 아닌지를 파악하기 위해서 visited를 3차원으로 만드는 것이 핵심이다.
visited = [[[[0 for _ in range(K + 1)] for _ in range(W)] for _ in range(H)]]
visited[0][0][0] = 1
왜 visited를 3차원으로 만들어야 하는지 처음엔 이해가 잘 안 갔다. 기존 코드의 경우에도 전체 움직인 수(move)와 말의 움직임(h_move)을 나타낸 수를 큐에 넣어서 기억하고 있었기 때문에 굳이 말의 움직임까지 3차원으로 만들면 방문처리하는 데에 시간이 더 많이 걸린다고 생각이 들었기 때문이다.
그렇다면..
어떤 좌표에 한 번 방문했다면 말처럼 왔는지, 원숭이처럼 왔는지가 차이가 있을까?
정답은, "그렇다" 다.
어떤 x 좌표를 도착한 상황일 경우, 크게 두 가지로 나누어보자.
만약, 이 경우에 x 좌표 이후에 장애물이 있다면? 2번 case에선 더이상 움직이지 못 할 것이다. 그치만 1번 case라면 말의 움직임을 사용해서 장애물을 뛰어넘을 수 있다. visited를 1차원 배열로 만들게 되면(처음 내가 풀이한 방법), 위와 같은 상황에서 말의 움직임을 써서 해당 위치에 도달한 경우가 더 빨랐을 때엔 visited가 이미 1이기 때문에 1번 case가 있음에도 불구하고 고려하지 못하게 된다.