6114 : 숨바꼭질 2 (경로 수)

시간 1.000s · 메모리 256MB · 제출 0 · 정답 0

코드제출 문제 풀기

채점기록 통계 묻고답하기

수빈이(N)가 동생(K)을 찾는 가장 빠른 시간과, 가장 빠른 시간으로 동생을 찾는 방법의 수가 몇 가지인지를 함께 구하는 프로그램을 작성하십시오. 이동 방식은 '숨바꼭질 1'과 동일합니다.

첫째 줄에 N과 K (0 ≤ N, K ≤ 100,000)가 공백 구분되어 주어집니다.

첫째 줄에 최단 시간, 둘째 줄에 그 최단 시간으로 도달할 수 있는 모든 방법의 가짓수를 출력합니다.

5 17

4
2

동일한 탐색 레벨(깊이)에서 다음 노드의 거리가 dist[next] == dist[curr] + 1인 경우, 방법의 가짓수 ways[next] += ways[curr]를 더해주어야 합니다.

BFS