BOJ 5811 낙하산 고리들¶
https://www.acmicpc.net/problem/5811
서브태스크 1¶
각각의 정점이 중요한 고리인지 O(N)에 확인하면 됩니다. 즉, 해당 정점을 지웠을 때 나머지가 체인으로 구성되어 있는지 확인하면 됩니다. 가장 간단한 방법은 다음 조건을 검사하는 것이라고 생각됩니다.
- 포레스트여야 합니다. 즉, 사이클이 없어야 합니다.
- 모든 정점의 차수가 2 이하여야 합니다.
서브태스크 2, 3¶
CountCritical이 호출될 때마다 모든 중요한 고리를 O(N)에 찾는 것이 목표입니다.
관찰 1. 정점을 지우면 나머지 정점의 차수가 최대 1 감소합니다. 따라서, 차수가 4 이상인 정점 v가 있으면 v만 중요한 고리가 될 수 있습니다. v가 아닌 정점을 지우면 v의 차수는 3 이상이라서 절대로 체인을 이룰 수 없기 때문입니다.
차수가 4 이상인 정점이 있으면 그중 아무거나 하나를 잡고 중요한 고리인지 확인하면 됩니다. 따라서 O(N)에 풀립니다. (그런 정점이 여러 개면 아무 것도 중요한 고리가 될 수 없지만, 그 경우를 따로 처리할 필요는 없습니다.)
이제 그런 정점이 없다고 가정합시다.
관찰 2. 차수가 3인 정점 v가 있으면 v 및 v에 인접한 정점만 중요한 고리가 될 수 있습니다.
차수가 3인 정점이 있으면, 그중 아무거나 하나를 잡고 그 정점 및 그에 인접한 정점 3개를 확인하면 됩니다. 후보가 4개이므로 O(N)에 풀립니다.
이제 그런 정점도 없다고 가정합시다. 모든 정점의 차수가 2 이하이면, 모든 연결 요소는 체인이거나 사이클입니다.
관찰 3. 사이클이 있으면 그 사이클에 있는 정점만 중요한 고리가 될 수 있습니다. 연결 요소 중 사이클이 없으면 답은 N, 하나이면 답은 그 사이클의 크기와 같고, 두 개 이상이면 답은 0입니다.
따라서 직접 정점을 지워볼 필요 없이 답을 그래프의 구조만 보고 알아낼 수 있습니다. 이번에도 O(N)에 풀립니다.
서브태스크 4, 5¶
간선을 추가하면서 위의 세 가지 관찰을 동적으로 관리하는 것이 목표입니다. 관찰 3부터 시작해서 거꾸로 올라가는 것이 좋습니다.
관찰 3 최적화¶
차수가 3 이상인 정점이 생기지 않는다는 가정 하에 답을 동적으로 관리하려면 [[분리 집합]]을 사용하면 됩니다. 분리 집합에 크기까지 추가로 저장해 둡시다. 이제 답은 두 단계에 걸쳐 바뀌는데,
- 처음에는 답이 N입니다.
- 이미 연결된 두 점이 연결될 경우 사이클이 하나 형성됩니다. 사이클이 처음으로 형성될 경우, 답은 해당 연결 요소의 크기와 같습니다.
- 이미 연결된 두 점이 또 연결될 경우 답은 0입니다.
그러다가 차수가 3인 정점이 생기는 순간, 이 자료구조를 파기하고 아래의 "관찰 2 최적화" 단락으로 넘어가면 됩니다. 정점의 차수는 그냥 배열로 관리하면 됩니다.
관찰 2 최적화¶
이제 새로운 자료구조를 생각해야 합니다. 후보가 최대 4개니까, 각각의 후보에 대해 "이 후보를 지웠을 때 나머지가 체인을 이루는가"를 판별할 수 있으면 좋을 것입니다. 즉 후보 v가 실제로 중요한 고리인지 확인하려면
- v와 연결된 간선을 모두 지우고,
- 나머지가 포레스트를 이루면서 최대 차수가 2인지 확인하고,
- 지운 간선을 모두 복원하면 됩니다.
하지만 간선을 지우는 건 일반적으로 매우 어려운 작업입니다.
이를 해결하려면 그 4개의 후보가 한 번 정해진 후로 바뀌지 않는다는 점을 활용하면 됩니다. (정확히는, 바꿀 필요가 없습니다.) 후보를 a, b, c, d라고 합시다. 간선을 하나 추가할 때마다 a를 지우고 확인한 다음 도로 추가하지 말고, 애초부터 a를 미리 지워놓고 간선이 추가될 때마다 확인해 줍시다. b, c, d도 마찬가지입니다.
즉 다음과 같은 자료구조를 a, b, c, d 하나씩 총 4개 만들면 됩니다.
- 이 자료구조는 특정 정점 v를 무시합니다.
- 간선을 추가하려고 할 때, 간선의 양끝 점 중 하나가 v이면 무시합니다.
- 그래프 전체가 체인으로 이루어져 있는지 검사합니다. 이는 서브태스크 1에서 제시한 방법을 쓰면 [[분리 집합]]으로 구현할 수 있습니다.
이 자료구조를 새로 만드는 순간, 지금까지 나왔던 Link 쿼리들을 전부 이 자료구조에 적용시켜야 합니다. 관찰 3에서 쓴 자료구조에서 Link 쿼리들을 저장해 뒀다가, 관찰 2로 넘어갈 때 그대로 Link해주면 됩니다.
관찰 1 최적화¶
관찰 1은 구현할 필요도 없습니다. 차수가 4 이상인 정점이 있든 없든 후보는 위에서 정한 a, b, c, d 중에 있다는 사실은 바뀌지 않습니다.
서브태스크 2, 3에서 관찰 1이 필요했던 이유는 차수가 매우 큰 정점에다가 그와 인접한 정점까지 다 확인하면 후보가 O(N)개나 되기 때문인데, 이미 관찰 2를 최적화하면서 후보를 O(1)개로 좁혀 버렸기 때문에 관찰 1은 이제 필요가 없습니다.
각 쿼리에 대한 시간 복잡도는 amortized O(logN)입니다.