임시 도로망 연결 상태 확인하기

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

today hard dynamic-connectivity 함수명: temporaryRoadNetworkStatus 제한 시간: 800ms

임시 도로가 켜지고 꺼지는 이벤트가 순서대로 주어질 때, 각 조회 시점마다 두 지점이 연결되어 있는지 반환하는 temporaryRoadNetworkStatus 함수를 작성하세요.

문제 설명

지점은 0번부터 n - 1번까지 있습니다.

events는 아래 세 종류의 이벤트로 이루어진 배열입니다.

["add", a, b]: 지점 a와 b를 잇는 임시 도로가 활성화됩니다.
["remove", a, b]: 지점 a와 b를 잇는 임시 도로가 비활성화됩니다.
["query", a, b]: 현재 활성화된 도로만 사용해서 a에서 b까지 갈 수 있는지 묻습니다.

모든 query 이벤트의 답을 순서대로 배열에 담아 반환하세요.

제한사항

1 <= n <= 100000
1 <= events.length <= 100000
각 이벤트의 a, b는 0 <= a, b < n을 만족합니다.
a와 b가 같은 query의 답은 항상 true입니다.
도로는 무방향입니다. 즉, [a, b]와 [b, a]는 같은 도로입니다.
이미 활성화된 도로가 다시 add되는 경우는 없습니다.
활성화되지 않은 도로가 remove되는 경우는 없습니다.
모든 도로가 이벤트 끝까지 활성 상태로 남을 수 있습니다.
반환값은 query 이벤트에 대한 불리언 배열입니다.
각 조회마다 그래프를 새로 탐색하면 큰 입력에서 시간 제한을 통과하기 어렵습니다.

예시

입력: n = 4, events = [["add", 0, 1], ["add", 1, 2], ["query", 0, 2], ["remove", 1, 2], ["query", 0, 2], ["add", 2, 3], ["query", 0, 3], ["add", 1, 2], ["query", 0, 3]] -> 출력: [true, false, false, true]
입력: n = 3, events = [["query", 0, 2], ["add", 0, 2], ["query", 0, 2], ["remove", 0, 2], ["query", 0, 2]] -> 출력: [false, true, false]

힌트

도로 하나는 add된 시점부터 remove되기 직전까지 하나의 활성 구간을 가집니다.
각 도로의 활성 구간을 시간축 세그먼트 트리에 넣으면, 어떤 노드의 시간 구간 전체에서 항상 켜져 있는 도로들을 모을 수 있습니다.
세그먼트 트리를 DFS로 내려가며 도로를 union하고, 노드 처리가 끝나면 union 전 상태로 되돌리는 구조를 생각해 보세요.

해설

이 문제는 온라인으로 보면 까다롭습니다. 일반 Union-Find는 두 집합을 합치는 데는 강하지만, 이미 합친 간선을 remove할 때 다시 분리하는 연산을 직접 처리하지 못합니다.

따라서 이벤트를 먼저 모두 읽고, 각 도로가 언제부터 언제까지 활성 상태였는지 구간으로 바꿉니다. 예를 들어 어떤 도로가 2번 이벤트에서 추가되고 7번 이벤트에서 제거되었다면, 이 도로는 시간 구간 [2, 6] 동안만 존재합니다. 끝까지 제거되지 않은 도로는 [addIndex, events.length - 1] 구간을 가집니다.

이제 시간축 위에 세그먼트 트리를 만들고, 각 도로의 활성 구간을 덮는 노드들에 그 도로를 저장합니다. 세그먼트 트리의 어떤 노드가 나타내는 시간 구간 전체에서는 그 노드에 저장된 도로들이 항상 활성 상태입니다.

DFS로 세그먼트 트리를 탐색하면서 현재 노드에 저장된 도로들을 rollback 가능한 DSU에 union합니다. 리프 노드에 도착하면 그 시점의 이벤트가 query인지 확인하고, 두 지점의 루트가 같은지 답합니다.

DFS가 노드에서 빠져나올 때는 해당 노드에서 수행한 union을 모두 되돌려야 합니다. 이를 위해 union 전에 변경된 부모와 크기 정보를 스택에 기록해 두고, 저장해 둔 스냅샷 크기까지 pop하면서 복구합니다.

각 도로 구간은 세그먼트 트리의 O(log m)개 노드에 들어가고, 각 union과 rollback은 거의 상수 시간에 처리됩니다. 따라서 전체 시간 복잡도는 O((m log m) * alpha(n))에 가깝고, 여기서 m은 이벤트 수입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과