[BOJ 17146] IZLET

문제: https://www.acmicpc.net/problem/17146

 

힌트 1 (Subtask 1):

$D_{i, j} = 1$ 인 두 $i, j$ 정점들을 모두 합치고 (같은 색으로 칠해주고) 나면, 모든 $i \ne j$에 대해 $D_{i, j} = 2$가 됩니다. 이 경우에는 색을 번갈아가면서 칠하면서 문제를 해결할 수 있습니다. 트리의 모양은 아무렇게나 정해도 상관 없습니다.

힌트 2 (Subtask 2):

$1, \cdots, N-1$ 까지의 색을 정했을 때 $N$의 색을 정한다고 해 봅시다. $i$에서 $N$까지 가는 경로 위에 있는 정점의 색 집합은 $i$에서 $N-1$까지 정점의 색 집합에다가 $N$의 색을 추가한 것입니다. 만약 $D_{i, N} \ne D_{i, N-1}$이라면 $i, i+1, \cdots, N-1$의 색이 모두 $i$와 다르다는 것입니다. 처음으로 $D_{k, N} = D_{k, N-1}$이 되는 $k$에 대해 $k$에 칠해진 색이 $i$에 칠해진 색이 됩니다.

풀이:

트리의 모양을 만들어봅시다. $D_{i, j} = 1$인 정점끼리 먼저 이어주고, $D_{i, j} = 2$인 정점끼리는 아무렇게나 이어주면 됩니다(스패닝트리를 만들면 됩니다.)

구체적인 이유는, $D_{i, j} = 2$인 간선으로 이루어진 BCC는 원래 그래프에서 두 가지 색이 번갈아 나오는 연결성분입니다. 이 연결성분 내부에서는 모두 $D_{i, j} = 2$이기 때문에 클리크를 이룹니다. 어차피 이 연결성분 안에 있는 두 정점을 거쳐가면 어떻게 하든 $2$가지 색을 보기 때문에 연결하는 방법은 중요하지 않습니다.

 

이제 색을 칠해 봅시다. 힌트 $2$의 관찰을 하나의 일직선 경로가 아니라 트리 위의 경로로 바뀌어도 성립합니다. 즉, 정점을 하나씩 추가합니다. 정점 $w$를 $v$에 붙여서 추가했다고 하면, $w$에서 시작하면서 DFS를 돌면서 가장 처음으로 $D_{k, v} = D_{k, w}$가 되는 점에서 $k$에 칠해진 색이 $w$에 칠해진 색과 같게 됩니다. (이전에 방문한 경로들에서는 모두 다른 색이었기 때문입니다.

 

이 두가지를 구현해주면 문제를 해결할 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/e55661c6d31046aaa56e2ab48612eb6d