SCPC 2017 본선 4번 풀이. 방 바꾸기

문제 설명

www.codeground.org 참조

풀이, Part 1 (부분문제 2)

원래 그래프를 G라고 하자. G에서 임의의 간선은 최대 하나의 사이클에만 속하므로, 사이클을 이루는 정점들을 하나로 묶은 그래프 T를 생각하자. 사이클을 이루지 않는 정점은 그대로 홀로 둔다. T는 트리가 된다. 왜냐면, T의 정점들이 사이클을 이룬다면 애초에 하나로 묶였을 것이기 때문이다.

* 원래 그래프의 정점과 구분하기 위해 T의 정점과 간선은 슈퍼정점과 슈퍼간선으로 표현할 것이다.

* INF = 무한대 (Infinity)의 약자로 쓸 것이다.

T의 슈퍼정점들 중, 빈 방의 처음 위치를 포함하는 슈퍼정점이 딱 하나 있을 것이다. 이 슈퍼정점을 트리 T의 루트 R(T)로 하자. 빈 방은 R(T)의 자식슈퍼정점 중 일부를 방문하고 돌아오거나, 방문한 후 그대로 그 안에 있거나 둘 중 하나이다. 따라서, T의 임의의 슈퍼정점 u에 대해 다음과 같이 몇 가지 비용을 정의하자. 또한, 슈퍼정점 u를 루트로 하는 T의 서브트리를 S(T, u)라고 하자.

• a[u] = 빈 방이 S(T, u)에 들어가 모든 정점을 최종 배치로 돌려놓고 나오는 데 필요한 최소 이동 횟수 (불가능하면 INF)
• b[u] = 빈 방이 S(T, u)에 들어가 모든 정점을 최종 배치로 돌려놓고 그 안에 머무르는 데 필요한 최소 이동 횟수 (불가능하면 INF)
• c[u] = 빈 방이 S(T, u) 내부 정점에서 내부 정점으로 움직여야 하는 최소 횟수 (불가능하면 INF)

슈퍼정점 u를 루트로 하는 T의 서브트리 S(T, u)의 최종 배치 중 빈 방이 있는 경우 무조건 a[u] = INF이고, 빈 방이 없는 경우 무조건 b[u] = INF이다.

또한, a[u]와 b[u]를 계산할 때 초기 빈 방 위치 및 a[u]를 계산할 때 최종 빈 방 위치는 슈퍼정점 u가 T에서 T의 부모와 연결되는 정점이라고 하자.

그러면 다음과 같은 점화식이 성립한다. 따라서 이 문제는 일종의 '트리 DP' 문제라고 할 수 있다.

• T의 서브트리 S(T, u)가 최종 배치에서 빈 방을 포함하지 않는 경우
•     a[u] = 2 + c[u] + Sum[T에서 u의 모든 자식 슈퍼정점 v에 대해](a[v])
•     b[u] = INF
• T의 서브트리 S(T, u)가 최종 배치에서 빈 방을 포함하며, 그 빈 방이 u 자체에 포함된 경우
•     a[u] = INF
•     b[u] = 1 + c[u] + Sum[T에서 u의 모든 자식 슈퍼정점 v에 대해](a[v])
• T의 서브트리 S(T, u)가 최종 배치에서 빈 방을 포함하며, 그 빈 방이 u의 자식 슈퍼정점 s에 포함된 경우
•     a[u] = INF
•     b[u] = 1 + c[u] + b[s] + Sum[T에서 s를 제외한 u의 모든 자식 슈퍼정점 v에 대해](a[v])

* 물론 u = R(T)인 경우 들어오고 나가는 비용 2, 1, 1이 없을 것이다. 따라서 최종해를 계산할 때는 a[R(T)]에서 2를, b[R(T)]에서는 1을 빼 주어야 한다.

지금까지의 논의는 G에 사이클이 없는 경우(부분문제 2)를 해결하기에 충분하다. 왜냐면 G에 사이클이 없는 경우 G = T(엄밀히 말하면 동형)이고 c[u]도 모두 0 아니면 INF이기 때문이다. 따라서 초기 배치에서 빈 방이 있는 위치를 루트 삼아 DFS를 하면서 a[u]와 b[u]를 재귀적으로 계산해주면 충분하다.

풀이, Part 2

만약 G에 사이클이 있는 경우, 더 이상 G = T가 아니다. 사이클을 어떻게 검출할 수 있을까? 이를 위해, 타잔(Tarjan)의 Strongly Connected Component (SCC) 알고리즘을 생각해보자. 타잔 알고리즘은 유향그래프에서 DFS를 수행하면서, 각 정점 u에 대해 u가 최초로 발견된 순서 DiscoverTime[u]을 기록한다. 일반적으로는 u의 서브트리 탐색이 끝나면 u와 일부 자식 정점들을 모아 새로운 SCC를 구성할 수 있지만, u의 서브트리 중 DiscoverTime이 u보다 빠른데 아직 SCC로 분리되지 못한 정점이 있다면 u의 탐색을 끝낼 때 새로운 SCC를 구성하지 않고 기다린다.

우리는 이와 동일한 방법을 사용해 주어진 무향그래프 G에서 사이클을 분리하는 데 활용할 수 있다. 위 알고리즘을 무향그래프에 적용하면 Biconnected Component를 분리해 내는데, 이 문제 조건에서 '하나의 간선은 최대 하나의 사이클에 포함된다'는 제약을 주었으므로 각 Biconnected Component는 단일 정점 혹은 사이클에 해당하기 때문이다.

풀이, Part 3

이제 c[u]를 계산하는 방법을 살펴보자. 빈 방이 슈퍼정점 u의 사이클 내에서 움직이는 데는 크게 두 가지 목적이 있다.

1. 사이클 내의 정점들을 회전시켜 최종 자리를 찾아가게 만들기 위해
2. 빈 방의 손길을 필요로 하는 자식 슈퍼정점을 방문하기 위해

목적 1만 있다고 생각해보면, 가능한 회전은 총 L * (L-1)가지이다. 빈 방이 L가지 위치 중 하나를 점하면, 나머지 L-1개의 위치는 원래의 순열이 회전하여 들어가는데 회전할 수 있는 방법이 L-1가지이기 때문이다. (* L = 슈퍼정점 u가 포함하는 사이클의 길이)

회전하여 최종 배치로 만드는 게 가능한지는 순열의 순서가 동일한지를 비교하면 되므로 O(L)에 수행할 수 있다.

가능할 때 필요한 최소 회전수는 시계방향과 반시계방향 중 더 좋은 것을 택하면 된다. 빈 방의 위치와 임의의 한 학생의 위치를 이용해 O(1)에 계산할 수 있다.

목적 2는 어떻게 고려해야 할까? 만약 목적 1만 고려할 때의 최소 회전 과정에서 전체 사이클을 커버한다면, 목적 2는 자동적으로 충족되므로 더 고려할 필요가 없다. 따라서 목적 1이 사이클을 충분히 돌지 않는 경우만 고려하면 된다.

이 경우 사이클에서 목적 1에 의해 커버되는 세그먼트가 있고, 나머지는 커버되지 않는다. 세그먼트의 시작점을 A, 끝점을 B라고 하면, A에서 a만큼을 커버되지 않은 쪽으로 왔다가 가고, B에서는 b만큼 추가로 갔다가 돌아가면 된다. 총 횟수 추가는 2 * (a+b)이다. 이때 a+b를 최소화하는 것은 아직 커버되지 않은 세그먼트에서 커버하게 될 양 끝 위치간 거리를 최대화하는 것과 동일하다. 따라서 해당 부분을 훑으면서 O(L) 안에 계산할 수 있다.

알고리즘이 굉장히 복잡하여 버그를 내기가 무척 쉬우므로, 머릿속으로 생각을 계속 정리하며 코딩하는 것이 중요한 문제. 테스트 케이스도 많이 만들어봐야 한다.

보충 설명

* c[u]를 계산할 때, 빈 방의 시작 지점은 해당 슈퍼정점을 구성하는 정점 중 부모 슈퍼정점의 정점과 연결되는 정점으로 한다.

빈 방의 최종 지점은 빈 방이 도로 돌아 나가야 하는 경우 시작 지점과 동일하게, 내부에 존재해야 하는 경우 해당 지점이나 해당 자식 슈퍼정점으로 들어가는 관문 정점으로 한다.