[BOJ 9521] 색칠 공부

https://www.acmicpc.net/problem/9521

서로 다른 색깔을 칠해야 함을 나타내는 연결관계의 그래프를 만든다. 방향이지만 무방향인 것처럼 생각해야 한다. 그래프의 out-degree가 1임을 이용해 대부분의 경우들을 eliminate해야 한다. 일반적인 모든 경우에 대해 어떻게 할 지 고민하다가 털린 쉬운 문제이다.

연결관계 그래프의 각 컴포넌트는 어떤 식으로 생겼을까?

1. 직선으로 생겼을 수도 있다.

2. 사이클을 이룰 수도 있다.

☆ 3. 그런데 사이클을 이루는 정점들에서는 다른 정점들로 나가는 degree가 존재할 수 없다. 자기들끼리 가리켜야 하니깐

4. 그래서, 그래프는 사이클들과 그 사이클들을 향해 뻗어있는 직선들로 이루어져 있을 것이다.

5. 물론, 직선 형태로 생긴 컴포넌트도 직선의 끝 정점이 자신을 향해 있어야 할 것이므로 '사이클을 향해 뻗어있다'고 말할 수 있을 것이다.

$n_i$개 정점으로 이루어진 직선에서는 $k \times {(k-1)}^{n_i-1}$개의 경우의 수가 있을 것이다.

사이클의 경우는 어떨까?

1개짜리 사이클은 $f(1) = k$개의 경우의 수가 있다. 2개짜리 사이클은 $f(2) = k(k-1)$개의 경우의 수가 있다. 3개짜리 사이클은 $f(3) = k(k-1)(k-2)$개의 경우의 수가 있다.

4개부터는 어떤 점화식을 얻어내야 할 것 같다. 이제는 모든 정점이 서로 다른 색깔을 가질 필요가 없으므로(4개짜리는 대각선에 있는 정점끼리는 다른 색을 가질 필요가 없다) 이들이 같은 색깔을 가지는 지 다른 색깔을 가지는 지 여부로 점화식을 분리해 낼 수 있을 것 같다.

정점을 $1$, $2$, $...$, $n$번으로 이름붙이자. 만약 $1$번 정점과 $n-1$번 정점이 같은 색을 가지고 있다면, $1$번부터 $n-2$번까지의 정점으로 이루어진 사이클을 칠하고 $k-1$개의 칠하는 가짓수($1$번 정점의 색 = $n-1$번 정점의 색과 달라야 할 것이다)가 있는 $n$번 정점을 칠하는 만큼의 가짓수가 있다: $(k-1)f(n-2)$. 반대로 두 정점이 다른 색을 가지고 있다면, 이번에는 $1$번부터 $n-1$번까지의 정점으로 이루어진 사이클을 칠하고 $k-2$개의 칠하는 가짓수가 있는 $n$번 정점을 칠하는 만큼의 가짓수가 있을 것이다: $(k-2)f(n-1)$.

따라서 $f(n) = (k-1)f(n-2) + (k-2)f(n-1)$.

그렇게 각 사이클에 대해서 사이클을 칠할 수 있는 방법의 수를 위 함수를 전처리함으로써 구할 수 있다. 그리고 각 사이클에 연결되어 있는 직선들은 사이클을 모두 채운 다음($f$ 함수값만큼의 가짓수가 있을 것이다.) 사이클에 가까운 순서로부터 채워나가면 각각 직전의 정점과만 다른 색으로 칠하면 되므로 $k-1$가지 가짓수로 채울 수 있다. 위에서 언급한 특수한 직선의 경우에도 $f(1) = k$를 생각하면 같은 식이 성립할 것이다.

따라서 답은 모든 사이클을 찾은 다음 각 사이클을 이루는 정점이 ${c}_{1}, ..., {c}_{t}$개씩이라면,

$$ {(k-1)}^{n - \sum_{i=1}^{t} {c}_{i} } \times \prod_{i=1}^{t} f({c}_{i}) $$

가 될 것이다.

그래프의 특수한 성질을 이용하여 가능한 그래프의 형태를 제한시켜 현실적인 점화식을 얻어냈다. 일반적인 그래프가 주어진다면 어떻게 풀 지는, 현실적인 시간 안에 풀 수가 있긴 할지는 고민해야 할 것 같다.