최단 메시지 경로 개수 세기
자바스크립트 코딩테스트 문제로 bfs-shortest-path-count 주제를 연습해보세요. 난이도는 medium이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.
문제 설명
메시지 서버들이 0번부터 n - 1번까지 번호로 주어지고, 두 서버를 직접 연결하는 통신선 목록 roads가 주어집니다.
모든 통신선의 이동 비용은 1로 같습니다. start 서버에서 target 서버까지 메시지를 보낼 때, 사용할 수 있는 최단 경로의 개수를 반환하는 countShortestMessageRoutes 함수를 작성하세요.
경로 개수가 매우 커질 수 있으므로 정답은 1,000,000,007로 나눈 나머지를 반환합니다.
제한사항
1 <= n <= 1000000 <= roads.length <= 2000000 <= start, target < nroads[i]는[a, b]형태이며,a번 서버와b번 서버가 양방향으로 연결되어 있다는 뜻입니다.- 같은 두 서버를 잇는 통신선은 중복해서 주어지지 않습니다.
- 자기 자신으로 이어지는 통신선은 주어지지 않습니다.
start와target이 같으면 길이 0의 경로 1개가 있으므로1을 반환합니다.target에 도달할 수 없으면0을 반환합니다.
예시
- 입력:
n = 6,roads = [[0, 1], [0, 2], [1, 3], [2, 3], [1, 4], [2, 4], [3, 5], [4, 5]],start = 0,target = 5-> 출력:4 - 입력:
n = 5,roads = [[0, 1], [1, 2], [0, 3], [3, 2], [2, 4], [1, 4]],start = 0,target = 4-> 출력:1 - 입력:
n = 4,roads = [[0, 1], [2, 3]],start = 0,target = 3-> 출력:0 - 입력:
n = 3,roads = [[0, 1], [1, 2]],start = 1,target = 1-> 출력:1
첫 번째 예시에서 0 -> 1 -> 3 -> 5, 0 -> 2 -> 3 -> 5, 0 -> 1 -> 4 -> 5, 0 -> 2 -> 4 -> 5 네 가지가 최단 경로입니다.
두 번째 예시에서는 0 -> 1 -> 4가 길이 2인 최단 경로입니다. 0 -> 1 -> 2 -> 4나 0 -> 3 -> 2 -> 4는 더 길기 때문에 세지 않습니다.
힌트
- 모든 간선의 비용이 같으므로 다익스트라보다 BFS가 적합합니다.
- 어떤 노드를 처음 방문한 순간 그 노드까지의 최단 거리가 정해집니다.
- 이미 최단 거리를 알고 있는 노드라도, 같은 거리로 다시 도착하는 경우에는 경로 개수를 더해야 합니다.
해설
무가중 그래프에서 최단 거리는 BFS로 구할 수 있습니다. 시작 노드에서 가까운 노드부터 차례로 방문하므로, 어떤 노드를 처음 만났을 때의 거리가 그 노드까지의 최단 거리입니다.
이 문제는 최단 거리뿐 아니라 최단 경로 개수도 함께 관리해야 합니다. 따라서 두 배열을 둡니다.
dist[i]:start에서i까지의 최단 거리ways[i]:start에서i까지 최단 거리로 가는 경로 개수
처음에는 dist[start] = 0, ways[start] = 1로 둡니다. BFS 중 현재 노드 cur에서 이웃 노드 next로 이동할 때 후보 거리는 dist[cur] + 1입니다.
만약 next를 처음 방문한다면 dist[next]를 후보 거리로 저장하고, ways[next] = ways[cur]로 둡니다. 현재 노드까지 가는 모든 최단 경로 뒤에 next로 가는 간선 하나를 붙이면 next까지의 최단 경로가 되기 때문입니다.
반대로 next가 이미 방문된 노드라도 dist[next] === dist[cur] + 1이라면, 현재 노드를 거쳐도 같은 최단 거리로 도착할 수 있다는 뜻입니다. 이때는 ways[next]에 ways[cur]를 더합니다.
dist[next]가 더 짧게 이미 정해져 있다면 현재 경로는 최단 경로가 아니므로 무시합니다.
이 방식은 각 노드와 간선을 BFS에서 한정된 횟수만 확인하므로 시간 복잡도는 O(n + roads.length)입니다. 인접 리스트와 거리, 경로 개수 배열을 사용하므로 공간 복잡도도 O(n + roads.length)입니다.
코드 작성
starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.
커스텀 테스트
함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]
실행 결과
아직 실행하지 않았습니다.
댓글
문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.