'BOJ.1600. 말이 되고픈 원숭이' 문제를 풀고 이러한 유형에 대해 더 깔끔하고 일반적으로 푸는 방법을 발견해서 새로 포스팅을 작성하게 되었다.
이 포스팅으로 문제 풀이 방식을 공부해보고, 비슷한 유형인 'BOJ.1600' 문제도 한 번 풀어보는 것을 추천한다.
📄 BOJ.2206. 벽 부수고 이동하기
문제 링크
다른 풀이 포스팅 링크
📄 BOJ.1600. 말이 되고픈 원숭이
문제 링크
풀이 포스팅 링크
📄 문제
백준
난이도 : Gold 3
문제 제목 : 벽 부수고 이동하기
✏️ 풀이 1
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
matrix = [list(map(int, list(input().strip()))) for _ in range(n)]
dy = (-1, 0, 0, 1)
dx = (0, -1, 1, 0)
def bfs():
deq = deque([[0, 0, 0]])
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
visited[0][0][0] = 1
while deq:
y, x, z = deq.popleft()
if y == n - 1 and x == m - 1:
return visited[y][x][z]
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if ny < 0 or nx < 0 or ny >= n or nx >= m:
continue
# 벽 부수지 않을때
if matrix[ny][nx] == 0 and visited[ny][nx][z] == 0:
visited[ny][nx][z] = visited[y][x][z] + 1
deq.append((ny, nx, z))
# 벽 부술 때
if matrix[ny][nx] == 1 and z == 0 and not visited[ny][nx][1]:
visited[ny][nx][1] = visited[y][x][0] + 1
deq.append((ny, nx, 1))
return -1
print(bfs())✅ 풀이 한줄 설명:
큐(deq)에 저장되는 요소는 [{y 좌표}, {x 좌표}, {벽을 부순 횟수}]로 구성된다.
방문 횟수를 관리하는 visited는 3차원 배열로, 다음과 같이 관리한다.
visited[{행}][{열}][{벽을 부순 횟수}] = {총 이동 횟수}
즉, 이번에 벽을 부수며 이동해서[4][5]에 도착했을 때, 이 경우에는 visited[4][5][1]에 visited[y][x][z + 1] + 1을 할당한다. (y, x, z는 이동 전 좌표와 이동 전 말로 이동한 횟수)
✅ 풀이 자세한 설명:
가장 마지막 '✨ 정리' 부분만 읽어봐도 괜찮다. 그러나 해당 부분을 읽고 코드를 봐도 이해가 안된다면 천천히 전체를 읽어보기 바란다.
🍎 문제 파악하기
우선 문제가 어떤 유형인지, 어떤 특이점이 있는지 파악한다.
- 기본적으로 BFS 문제이다. 현재 위치에서 정해진 규칙으로 다른 칸으로 이동할 수 있고,
0은 이동 가능한 곳,1은 이동 불가능한 벽이라는 부분에서 BFS 문제임을 알 수 있다. - 특이점에 대해 정리한다. 일반적인 BFS와 달리 '
k번 특정 방식으로 이동할 수' 있다. 끝점까지의 최단거리를 구하는 문제로, 특정 방식(벽 부수기)으로 이동한 경로가 최단 거리가 될 수도 있다.
🍎 특이점으로 인한 상황 파악하기
특이점이 있다면 그로 인해 고려해야 할 사항들을 파악한다.
특정한 이동 방식에 횟수가 제한될 때, 방문 처리 배열을 3차원으로 나타내는 것이 좋다. 즉, visited[{행}][{열}][{벽을 부순 횟수}] = {총 이동 수}로 나타낸다.
✨ 정리
정리하자면 풀이는 다음과 같다.
- 기본적으로 BFS 문제 풀이이다. 그러나
k번 '벽으로 이동 가능'하기 때문에 방문 처리 배열을 3차원으로 한다. (visited[{행}][{열}][{특정 이동 방식 사용 수}] = {총 이동 수})
💫 추가 팁!
# 벽 부술 때
if matrix[ny][nx] == 1 and z == 0 and not visited[ny][nx][1]:
visited[ny][nx][1] = visited[y][x][0] + 1
deq.append((ny, nx, 1))벽을 부술 때의 처리 작업에서, 많은 사람들이 마지막 조건인 not visited[ny][nx][1]을 해주지 않는 것을 보았다.
그러나 그렇게 되면 visited[ny][nx][1]에 이미 방문했을 때 필요없는 더 큰 방문 횟수 값이 덮어씌워질 수도 있다.
다음은 그 예시 입력들이다.
- 입력 값:
7 2
00
10
01
01
01
01
00
올바른 결과 값: 8 - 입력 값:
4 4
0000
0100
1111
0000
올바른 결과 값: 7
not visited[ny][nx][1]를 넣든 넣지 않든 반환 값은 동일하겠지만, 넣어야 필요없는 (더 큰 방문 횟수) 값이 덮어씌워지지 않는다.
실제로 1번 예시 입력에 대해 해당 조건을 넣은 경우와 넣지 않은 경우, 끝점에 도달했을때 visited를 확인해보면 다음과 같다.
[1, 0]을 주의하며 방문 경로를 한 번 돌려보면, 해당 조건을 넣지 않은 경우
[0, 0]에서 이미 [1, 0]에 대해 deq에 요소를 추가하고 visited[1][0][1] = 2도 해주었는데
[1, 1]에서 다시 [1, 0]에 대해 deq에 한 번 지나갔던 요소를 추가하고, visited[1][0][1] = 4를 해주는 것을 볼 수 있다.
답에 영향을 주진 않지만 쓸모없는 연산을 해주는 것이므로 조건을 더 엄격하게 추가하는 것이 좋다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '2206. 벽 부수고 이동하기'
GitHub - [9강] BFS/응용문제 '2206. 벽 부수고 이동하기'
이전에 이 문제를 풀고 나름 뿌듯해서 포스팅으로 정리까지 해두었는데, 'BOJ.1600. 말이 되고픈 원숭이' 문제를 풀고 보니 이 유형에 대해서는 3차원 배열로 방문 처리를 하는 것이 유리하다는 것을 배우고 다시 정리하게 되었다.
기억하자!
💫 BFS에서 특정한 이동 방식에 횟수가 제한될 때, 방문 처리를 3차원으로 나타낸다.
visited[{행}][{열}][{특정 이동 방식 사용 수}] = {총 이동 수}
