✓

태그:

23. DFS와 BFS CLASS 4 ESSENTIAL

두 종류의 최소 거리가 필요합니다.

풀이 비스무리한거 보기

미로에서 벽을 부술 기회가 한 번 있을 때, 최단 거리를 구하는 문제입니다. 단순 BFS로 풀기에는 벽을 허물 수 있다는 점이 신경쓰입니다. 따라서 최단 거리를 구할 때 벽을 부수지 않았을 때의 최단 거리, 벽을 부수었을 때의 최단 거리의 총 두 가지의 최단 거리를 동시에 다루어야 합니다. 또한 BFS를 사용할 때 점의 좌표는 물론, 벽을 부수었는지 여부도 포함해야 최단 거리를 구할 수 있습니다. BFS를 진행할 때 알고리즘은 아래와 같습니다.

1. 벽을 부수지 않은 경로에서 길로 이동할 때
   • 부수지 않은 경우 점까지의 최단 거리를 부수지 않은 경우의 최단 거리를 사용하여 업데이트
2. 벽을 부수지 않은 경로에서 벽으로 이동할 때
   • 부순 경우 점까지의 최단 거리를 부수지 않은 경우의 최단 거리를 사용하여 업데이트
3. 벽을 부순 경로에서 길로 이동할 때
   • 부순 경우 점까지의 최단 거리를 부순 경우의 최단 거리를 사용하여 업데이트

이렇게 하면 알맞은 답을 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-25 23:36:21

---