Number of Provinces

도시를 순서대로 살펴보세요. 이전 탐색에서 표시하지 않은 도시를 만나면, 각 탐색이 해당 성의 모든 도시를 표시하므로 이미 센 성에 속할 수 없습니다. 따라서 개수를 1 늘린 다음, 이 도시에서 도달할 수 있는 모든 도시를 표시하세요.

도시들을 찾으려면 스택을 사용하세요. 도시를 꺼내 행렬에서 해당 도시의 행을 읽고, 그 행에서 값이 1이며 아직 표시되지 않은 모든 도시를 스택에 넣으면서 표시하세요. 두 번째 예제에서는 도시 0에서 시작한 탐색이 도시 1을 스택에 넣고, 이어서 도시 1의 행이 도시 2를 추가합니다. 행 0에서 도시 2의 값이 0이어도 마찬가지입니다. 이런 식으로 각 행을 따라가야 다른 도시를 거쳐서만 연결된 도시도 찾을 수 있습니다.

각 도시는 한 번씩 꺼내지며, 도시를 꺼낼 때마다 n개의 항목이 있는 해당 행을 읽으므로 전체 시간 복잡도는 O(n²)입니다. 행렬을 한 번 읽기 때문입니다. 표시 정보와 스택에는 최대 n개의 도시가 들어가므로 추가 공간 복잡도는 O(n)입니다.

재귀 탐색은 더 간결하게 읽히지만, 하나의 긴 선 모양으로 된 성에서는 호출이 도시마다 한 단계씩 중첩됩니다. n = 150일 때는 안전하지만, 노드가 10^5개인 그래프에서 같은 코드를 실행하면 호출 스택이 넘칩니다. 그러므로 명시적인 스택을 사용하는 습관을 들이는 것이 좋습니다.

질문을 뒤집어 생각해 보세요. 도시마다 하나씩, n개의 지역에서 시작합니다. 행렬의 1은 두 도시가 같은 그룹에 속한다는 뜻입니다. 두 도시가 아직 서로 다른 그룹에 있다면 그룹을 합치고, 개수는 1 감소합니다. 마지막 도로를 처리한 뒤의 개수가 답입니다. 행렬은 대칭이고 대각선은 도시를 자기 자신과 연결하므로 대각선 위쪽의 항목만 확인하면 됩니다. 두 번째 예시에서는 개수가 5에서 시작합니다. (0, 1)의 1은 도시 0과 1을 합칩니다(4개 남음). (1, 2)의 1을 처리할 때는 도시 1이 도시 0의 그룹에 속한다는 것을 확인하고 도시 2를 그 그룹에 합칩니다(3개 남음). 도시 3과 4는 대각선 위쪽에 1이 없으므로 답은 3입니다.

서로소 집합 합집합이라고도 하는 유니온 파인드는 각 그룹을 트리로 저장합니다. parent[c]는 한 단계 위를 가리키며, 부모가 자기 자신인 꼭대기의 도시는 해당 그룹의 루트입니다. find가 두 도시를 각각 위로 따라가 같은 루트에 도달할 때, 두 도시는 같은 그룹에 속합니다. 두 그룹을 합치려면 한쪽 루트가 다른 쪽 루트를 가리키게 합니다.

두 가지 규칙으로 트리를 평평하게 유지합니다. 랭크에 따른 합치기는 짧은 트리를 긴 트리 아래에 붙입니다. 따라서 높이가 h인 트리에는 최소 2^h개의 도시가 있고, 어떤 경로도 log n보다 길지 않습니다. 경로 압축은 한 단계 더 나아갑니다. find가 루트를 찾으면, 거쳐 간 모든 도시가 그 루트를 곧바로 가리키도록 하므로 다음에는 그 도시들 중 어느 곳에서 조회하더라도 한 단계만 걸립니다. 두 규칙을 모두 적용하지 않으면, 운이 나쁜 순서로 긴 사슬의 도시들을 합칠 때 트리가 하나의 경로가 되어 모든 find가 O(n)단계를 거칩니다.

두 규칙을 모두 적용하면 각 find의 분할 상환 비용은 O(α(n))입니다. α는 역 아커만 함수이며, 컴퓨터가 저장할 수 있는 어떤 n에 대해서도 4를 넘지 않습니다. 행렬을 읽는 데 여전히 O(n²)이 걸리므로 이것이 전체 시간 복잡도이며, 부모 배열과 랭크 배열은 O(n) 공간을 차지합니다. 도로가 한 번에 하나씩 추가될 때 이 자료 구조의 장점이 드러납니다. 새 도로가 추가될 때마다 다시 탐색하지 않고도 개수를 최신 상태로 유지합니다.