이전에 풀었던 'BOJ.2206. 벽 부수고 이동하기' 문제의 상위호환 문제라고 생각한다. 이 문제를 바로 풀기 어려운 사람은 '벽 부수고 이동하기' 문제부터 풀어보기를 추천한다.
📄 BOJ.2206. 벽 부수고 이동하기
문제 링크
풀이 포스팅 링크1
풀이 포스팅 링크2 <- 추천!
📄 문제
백준
난이도 : Gold 3
문제 제목 : 말이 되고픈 원숭이
✏️ 풀이 1
import sys
from collections import deque
input = sys.stdin.readline
k = int(input())
w, h = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(h)]
dy = (1, 2, 2, 1, -1, -2, -2, -1, -1, 0, 0, 1)
dx = (-2, -1, 1, 2, 2, 1, -1, -2, 0, -1, 1, 0)
def bfs():
visited = [[[-1] * (k + 1) for _ in range(w)] for _ in range(h)] # y 좌표, x 좌표, 말 이동 수
deq = deque([[0, 0, 0]]) # y 좌표, x 좌표, 말 이동 수
visited[0][0][0] = 0
while deq:
y, x, z = deq.popleft()
if y == h - 1 and x == w - 1:
return visited[y][x][z]
if z < k:
for i in range(8):
ny = y + dy[i]
nx = x + dx[i]
if ny < 0 or nx < 0 or ny >= h or nx >= w:
continue
if graph[ny][nx]:
continue
if visited[ny][nx][z + 1] != -1:
continue
deq.append([ny, nx, z + 1])
visited[ny][nx][z + 1] = visited[y][x][z] + 1
for i in range(8, 12):
ny = y + dy[i]
nx = x + dx[i]
if ny < 0 or nx < 0 or ny >= h or nx >= w:
continue
if graph[ny][nx]:
continue
if visited[ny][nx][z] != -1:
continue
deq.append([ny, nx, z])
visited[ny][nx][z] = visited[y][x][z] + 1
return -1
print(bfs())✅ 풀이 한줄 설명:
큐(deq)에 저장되는 요소는 [{y 좌표}, {x 좌표}, {말로 이동한 횟수}]로 구성된다.
방문 횟수를 관리하는 visited는 3차원 배열로, 다음과 같이 관리한다.
visited[{행}][{열}][{말로 이동한 횟수}] = {총 이동 횟수}
즉, 원숭이가 이번에 말로 이동해서[4][5]에 도착했을 때, 이제까지 말로 이동한 횟수가 2번이라고 하자. 이 경우에는 visited[4][5][2]에 visited[y][x][z + 1] + 1을 할당한다. (y, x, z는 이동 전 좌표와 이동 전 말로 이동한 횟수)
✅ 풀이 자세한 설명:
가장 마지막 '✨ 정리' 부분만 읽어봐도 괜찮다. 그러나 해당 부분을 읽고 코드를 봐도 이해가 안된다면 천천히 전체를 읽어보기 바란다.
🍎 문제 파악하기
우선 문제가 어떤 유형인지, 어떤 특이점이 있는지 파악한다.
- 기본적으로 BFS 문제이다. 현재 위치에서 정해진 규칙으로 다른 칸으로 이동할 수 있고,
0은 이동 가능한 곳,1은 이동 불가능한 벽이라는 부분에서 BFS 문제임을 알 수 있다. - 특이점에 대해 정리한다. 일반적인 BFS와 달리 '
k번 특정 방식으로 이동할 수' 있다. 끝점까지의 최단거리를 구하는 문제로, 특정 방식(말)으로 이동한 경로가 최단 거리가 될 수도 있다.
🍎 특이점으로 인한 상황 파악하기
특이점이 있다면 그로 인해 고려해야 할 사항들을 파악한다.
특정한 이동 방식에 횟수가 제한될 때, 방문 처리 배열을 3차원으로 나타내는 것이 좋다. 즉, visited[{행}][{열}][{특정 이동 방식 사용 수}] = {총 이동 수}로 나타낸다.
✨ 정리
정리하자면 풀이는 다음과 같다.
- 기본적으로 BFS 문제 풀이이다. 그러나
k번 '말로 이동 가능'하기 때문에 방문 처리 배열을 3차원으로 한다. (visited[{행}][{열}][{특정 이동 방식 사용 수}] = {총 이동 수})
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '1600. 말이 되고픈 원숭이'
GitHub - [9강] BFS/응용문제 '1600. 말이 되고픈 원숭이'
이 문제를 처음 읽었을 때, 이전에 풀었던 'BOJ.2206. 벽 부수고 이동하기' 문제가 생각났다. 따라서 비슷하게 풀면 될거라 생각했는데, 시간 초과나 메모리 초과가 발생했다.
몇 시간 끙끙대다가 다른 사람들 풀이를 봤더니 다들 3차원 배열을 사용하는 것을 확인하고 ㅇㅁㅇ됐다.
알고보니 'BOJ.2206. 벽 부수고 이동하기' 문제도 다른 사람들은 일반적으로 3차원 배열을 사용하며 풀었던 것이었다!
나만 또 복잡하게 풀었지... 'BOJ.2206'도 3차원 배열로 푸는 방법으로 포스팅 정리를 해놔야겠다.
아무튼 이로 인해 알게 된 중요 포인트는 이것이다.
💫 BFS에서 특정한 이동 방식에 횟수가 제한될 때, 방문 처리를 3차원으로 나타낸다.
visited[{행}][{열}][{특정 이동 방식 사용 수}] = {총 이동 수}
