BOJ 3351. 삼각 분할
문제 해석
볼록 \(N\)각형의 삼각분할이 주어져 있고, 각 삼각형은 \(N\)가지 색 중 하나로 색칠되어 있다. 이 삼각분할에 사용된 diagonal 중 몇 개를 선택한 다음 그 diagonal들을 따라 잘라서 여러 다각형으로 쪼개려고 하는데, 같은 색의 삼각형들은 같은 다각형에 포함되도록 하고 싶다. 고를 수 있는 diagonal 개수의 최댓값을 구하라.
접근
Lemma. 단순다각형의 삼각분할에서 각 삼각형을 정점으로 하고, 두 삼각형이 변을 공유하면 해당 정점들 사이에 간선을 그어서 만든 그래프는 tree이다. 어렵게 말하면, 단순다각형의 삼각분할을 (outer face를 제외하고) 평면그래프로 보고 dual을 취하면 tree가 된다.
Proof. 단순다각형의 꼭짓점의 개수 \(k\)에 대하여 수학적 귀납법을 한다. \(k=3\)이면 결과 그래프는 정점 하나이므로 tree이다. \(k>3\)에 대하여 아무 diagonal을 따라 단순\(k\)각형 \(P\)를 자르면 단순\(k_1\)각형 \(P_1\)과 단순\(k_2\)각형 \(P_2\)를 얻을 것이고, \(k1<k, k2<k\)이므로 귀납 가정에 의해 \(P_1\)과 \(P_2\)로 얻는 그래프는 둘 다 tree이다. 이제 잘랐던 diagonal을 따라 \(P_1\), \(P_2\)를 도로 합치면 서로 다른 두 트리에서 정점을 하나씩 골라 간선으로 잇게 되므로 최종 그래프도 역시 tree이다.
즉, 정점마다 색이 칠해진 트리에서 같은 색의 정점 사이에는 항상 경로가 있도록 간선을 최대한 많이 지우라는 문제이다.
Tree의 루트를 정하고 모든 정점들에 \(0\)의 초기값을 준 다음, 모든 색 \(c\)에 대하여 색이 \(c\)인 정점들의 LCA의 값에 색이 \(c\)인 정점들의 개수를 더한다. 그랬을 때 임의의 subtree에 대하여 정점들의 값의 총합 이 정점 개수 와 일치하는 것은 그 subtree의 루트와 부모를 잇는 간선을 자를 수 있는 필요충분조건이 된다. Subtree가 한 색의 정점을 전부 포함하고 있으면 subtree 속 누군가의 값에 그 개수가 들어가겠지만, 어떤 색을 일부만 포함하면 그 개수만큼 subtree 밖으로 빠져나가기 때문이다.
Small-to-large로 더 많이 푸는 것 같은데 이 풀이는 이해한다면 추가하겠다.