✓

태그:

CLASS 4

1697번 문제랑 비슷하기는 한데 모든 경우의 수를 세려면 노드를 큐에 넣을 조건을 조금 널널하게 잡아야 할 것 같은데…??

풀이 비스무리한거 보기

1697번 - 숨바꼭질 문제와 조건은 거의 비슷하나 최단 시간에 도착하는 모든 경우의 수를 구하는 문제입니다. 1697번 문제의 BFS를 이용해서 최단 시간을 구하는 과정에서 큐에 추가할 위치까지 시간이 이전에 기록된 시간보다 크거나 같으면 큐에 넣지 않았는데, 최단 시간인 경로를 모두 구하려면 클 때만 큐에 집어넣지 않아야 합니다. 예를 들어 3에서 5로 가는 경로를 찾는다고 할 때, 3-4-5와 3-6-5의 두 경우가 있는데, 4와 6에서 각각 5를 큐에 집어넣을 때 둘 모두 포함시키기 위함입니다. 이렇게 하면 가능한 모든 최단 경로의 가짓수를 얻을 수 있습니다.

소스 코드

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

---