문제 링크(Link)
https://www.acmicpc.net/problem/2206
문제 해결(Solution)
1. BFS의 응용문제.
주의할 점 || 생각해볼 점(Caution || Consideration)
1. 만약 벽의 좌표를 모두 저장한 후, 하나씩 부수며 BFS를 하면 시간복잡도 O(NM(N+M))이 되므로 시간 초과를 받을 수 밖에 없다.
2. 보통은 2차원 배열을 이용해서 문제를 해결하지만, 이 문제는 3차원 배열을 이용하면 단 한번의 BFS를 통해서 답을 구할 수 있다.
3. dist[i][j][k] = (i, j)에서 k가 1이면 벽을 만나서 부수고 이동, k가 0이면 벽을 만나면 이동 불가.
참고(Reference)
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > 그래프_최단 거리' 카테고리의 다른 글
BOJ 16236 - 아기 상어 (0) | 2018.03.14 |
---|---|
BOJ 4179 - 불! (3) | 2017.11.03 |
BOJ 9370 - 미확인 도착지 (0) | 2017.07.29 |