일방통행 지도에서 반드시 지나는 체크포인트

자바스크립트 코딩테스트 문제로 dominator-tree 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard dominator-tree 함수명: mustPassCheckpoints 제한 시간: 500ms

문제 설명

0번부터 n - 1번까지의 체크포인트와 일방통행 도로 목록 roads가 주어집니다.

start에서 target으로 가는 모든 가능한 경로가 반드시 지나야 하는 중간 체크포인트를 오름차순 배열로 반환하는 mustPassCheckpoints 함수를 작성하세요.

단, start와 target 자체는 정답에 포함하지 않습니다.

제한사항

2 <= n <= 100000
0 <= roads.length <= 200000
roads[i]는 [from, to] 형태입니다.
0 <= from, to < n
from !== to
같은 방향의 도로가 여러 번 주어질 수 있습니다.
0 <= start, target < n
start !== target
start에서 target으로 갈 수 없다면 빈 배열 []을 반환합니다.
반환 배열은 체크포인트 번호 오름차순이어야 합니다.

예시

입력: n = 6, roads = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4], [4, 5], [3, 5]], start = 0, target = 5 -> 출력: [3]
입력: n = 7, roads = [[0, 1], [1, 2], [2, 6], [0, 3], [3, 4], [4, 6], [1, 4], [3, 2]], start = 0, target = 6 -> 출력: []
입력: n = 8, roads = [[0, 1], [1, 2], [2, 3], [3, 6], [0, 4], [4, 2], [3, 5], [5, 6], [6, 7]], start = 0, target = 7 -> 출력: [2, 3, 6]
입력: n = 4, roads = [[0, 1], [2, 3]], start = 0, target = 3 -> 출력: []

힌트

방향 그래프에서 “모든 경로가 반드시 지난다”는 조건은 start 기준의 지배자(dominator) 관계로 볼 수 있습니다.
target의 dominator 조상들은 start에서 target으로 가는 모든 경로에 포함됩니다.
큰 그래프에서는 각 후보 정점을 하나씩 제거하며 BFS/DFS를 반복하면 시간 제한을 넘기 쉽습니다.

해설

이 문제는 무방향 그래프의 단절점 문제가 아닙니다. 도로가 일방통행이고 사이클이 있을 수 있으므로, 어떤 정점 하나를 제거했을 때 그래프가 나뉘는지만 보면 정답을 놓칠 수 있습니다.

핵심은 start에서 출발하는 모든 경로에서 특정 정점이 항상 먼저 등장해야 하는지를 판단하는 것입니다. 이런 정점을 그래프 이론에서는 지배자(dominator)라고 부릅니다.

풀이 흐름은 다음과 같습니다.

start에서 DFS를 하며 실제로 도달 가능한 정점만 방문 순서로 번호를 붙입니다.
DFS 트리의 역간선 정보를 이용해 각 정점의 semi-dominator를 계산합니다.
Lengauer-Tarjan 알고리즘의 union-find 평가 구조로 각 정점의 immediate dominator를 구합니다.
target이 방문되지 않았다면 []을 반환합니다.
target에서 immediate dominator 부모를 따라 start 전까지 올라가며 만나는 정점들을 모읍니다.
문제 요구에 맞게 정점 번호 오름차순으로 정렬해 반환합니다.

예를 들어 세 번째 예시에서는 0 -> 1 -> 2 -> 3 -> 6 -> 7과 0 -> 4 -> 2 -> 3 -> 5 -> 6 -> 7처럼 여러 경로가 존재합니다. 1과 4는 서로 대체될 수 있지만, 어느 경로를 선택해도 2, 3, 6은 반드시 지나야 합니다.

각 간선과 정점은 알고리즘 과정에서 거의 상수 횟수만 처리되므로 전체 시간 복잡도는 O((n + roads.length) log n) 수준으로 잡을 수 있습니다. 경로 압축 평가를 엄밀히 구현하면 실질적으로 선형에 가깝게 동작합니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과