서버 종료 뒤 활성 네트워크 개수

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

today hard union-find 함수명: solution 제한 시간: 300ms

n개의 서버와 양방향 연결 정보 edges, 그리고 순서대로 종료할 서버 번호가 담긴 shutdownOrder가 주어질 때, 각 종료 직후 남아 있는 활성 서버들끼리 이루는 연결 네트워크의 개수를 반환하는 solution 함수를 작성하세요.

제한사항

서버 번호는 1부터 n까지입니다.
1 <= n <= 100000
0 <= edges.length <= 200000
1 <= shutdownOrder.length <= n
edges[i] = [a, b]는 a와 b를 잇는 양방향 연결을 뜻합니다.
자기 자신으로 가는 간선은 없고, 같은 간선이 중복으로 주어지지 않습니다.
shutdownOrder의 서버 번호는 모두 서로 다릅니다.
종료된 서버는 비활성 상태가 되며, 비활성 서버가 포함된 간선은 연결에 기여하지 않습니다.
어떤 시점에 활성 서버가 하나도 없으면 네트워크 개수는 0입니다.

예시

입력:
- n = 5
- edges = [[1, 2], [2, 3], [3, 4], [4, 5], [2, 5]]
- shutdownOrder = [2, 5, 3] → 출력: [2, 2, 2]
입력:
- n = 4
- edges = [[1, 2], [2, 3], [3, 4]]
- shutdownOrder = [2, 3, 1, 4] → 출력: [2, 2, 1, 0]

힌트

종료를 앞에서부터 그대로 시뮬레이션하면, 매번 그래프를 다시 쪼개 봐야 해서 비효율적입니다.
삭제는 어렵고 추가는 쉽다는 관점으로 뒤집어 생각해 보세요.
모든 종료가 끝난 상태에서 시작한 뒤, shutdownOrder를 거꾸로 보며 서버를 하나씩 다시 켜면 유니온-파인드로 빠르게 합칠 수 있습니다.

해설

정방향으로 보면 서버가 하나씩 삭제됩니다. 하지만 유니온-파인드(Disjoint Set Union)는 연결 요소를 합치는 작업에는 강하지만, 이미 합쳐진 것을 다시 분리하는 작업은 잘 못합니다.

그래서 이 문제는 순서를 뒤집어 푸는 것이 핵심입니다.

1) 모든 종료가 반영된 최종 상태를 먼저 만든다

shutdownOrder에 들어 있는 서버들을 전부 비활성이라고 표시합니다. 그러면 남아 있는 서버들만으로 이루어진 초기 그래프를 만들 수 있습니다.

이 상태에서:

활성 서버를 하나 켤 때마다 네트워크 수는 일단 1 증가합니다.
이미 활성인 이웃 서버와 연결되면, 서로 다른 네트워크 두 개가 하나로 합쳐지므로 네트워크 수를 1 감소시킵니다.

2) 종료 순서를 거꾸로 보며 서버를 복구한다

예를 들어 종료 순서가 [2, 5, 3]이었다면, 역순 복구는 [3, 5, 2]입니다.

각 단계에서:

해당 서버를 활성화한다.
그 서버와 연결된 이웃 중 이미 활성인 서버들과 union 한다.
현재 네트워크 수를 기록한다.

이렇게 얻은 값은 복구 직후의 상태이므로, 다시 뒤집으면 우리가 원하는 종료 직후의 상태와 맞춰낼 수 있습니다.

3) 왜 정답이 되는가?

정방향에서 k개를 종료한 뒤의 활성 서버 집합은, 역방향에서 shutdownOrder의 뒤쪽 서버들을 복구한 어느 시점의 활성 서버 집합과 정확히 같습니다.

즉, 같은 활성 서버 집합을 서로 반대 방향에서 보고 있을 뿐이라서, 연결 네트워크 개수도 동일합니다.

4) 구현 포인트

각 서버의 인접 리스트를 미리 만듭니다.
parent, size 배열로 유니온-파인드를 구성합니다.
active 배열로 현재 서버가 켜져 있는지 관리합니다.
어떤 서버를 활성화할 때 네트워크 수를 먼저 +1 하고, 활성 이웃과 union 할 때마다 실제로 다른 집합이었다면 -1 합니다.

이 방법의 시간 복잡도는 인접 리스트 구성까지 포함해 대략 O((n + m + q) * α(n)) 수준으로, 큰 입력도 충분히 처리할 수 있습니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.