👉 2206 벽 부수고 이동하기
[정답 코드]
from collections import deque
import sys
input = sys.stdin.readline
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(matrix, visited, d):
res = inf
while d:
x, y, flag = d.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]):
if matrix[nx][ny] == 1 and flag == 0: # 벽 부수기
# matrix[nx][ny] = 0
if visited[nx][ny][1] == 0:
visited[nx][ny][1] = visited[x][y][0] + 1
d.append((nx, ny, 1))
elif matrix[nx][ny] == 0:
if visited[nx][ny][flag] == 0:
visited[nx][ny][flag] = visited[x][y][flag] + 1
d.append((nx, ny, flag))
row, col = map(int, input().split())
matrix = [list(map(int, input().rstrip())) for i in range(row)]
visited = [[[0, 0] for i in range(col)] for j in range(row)]
d = deque()
d.append((0, 0, 0))
visited[0][0][0], visited[0][0][1] = 1, 1
bfs(matrix, visited, d)
if max(visited[-1][-1]) == 0:
print(-1)
elif min(visited[-1][-1]) == 0:
print(max(visited[-1][-1]))
else:
print(min(visited[-1][-1]))[풀이]
문제의 조건 상 벽을 최대 한 개 부술 수 있다.
처음 생각한 아이디어는 다음과 같다.
- bfs를 진행하면서 벽을 만나면 벽을 깬 후 bfs_after_break() 를 진행하여 도착지점에 결과값을 갱신한다.
- 시간초과.. 여러 반례를 넣어보며 맞왜틀?을 시전했다. (시간초과인 이유는 뒤에 설명한다.)
여러 질문들을 보며 3차원 배열을 사용해야 한다는 아이디어를 참고했고, 위와 같은 코드가 완성되었다.
- 3차원 배열의 세 번째 축은 두 경우(벽을 깼을 때, 깨지 않았을 때)를 나누기 위한 축이다.
- 벽을 만나고 벽을 한번도 깬 적이 없는 상태라면(
if matrix[nx][ny] == 1 and flag == 0:) 벽을 부수고 세 번째 인자(flag)를 0 에서 1로 바꾸어준다.
✔ 최단거리 = bfs
대부분 최단거리 문제는 bfs로 푸는 것을 공식처럼 알고 있다. 왜 bfs일까?
bfs는 너비 우선 탐색이다. 트리로 생각해보면 한 level씩 내려가며 검사하는 것이다. 그렇기에 도착점에 도착하는 순간 바로 그 경로가 최단거리가 된다.
bfs를 구현할 때 매번 잘못 생각하던 포인트가 두 가지 있다.
1. 내가 검사하는 칸이 이미 방문된 지점일 때 최솟값으로 갱신할 수 있는지의 여부
2. bfs 과정 중 한 지점을 방문한 상태에서 새로운 함수를 통해 도착점까지 가서 최솟값을 갱신하고자 함(벽 부수기 문제 -> 시간초과)
1번 : 불가능하다. 너비 우선 탐색이기 때문에 방문한 순간 그 자체가 최단거리다.
2번 : bfs와 dfs의 혼종인가..싶다. 최솟값을 갱신하려는 생각 자체를 버리자.
[적용 자료구조 및 알고리즘]
- BFS
