[BOJ] 9521번: PALETA

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

맨 처음에는 문제를 조금 쉽게 생각했는데 생각보다 많이 어려운 문제였습니다. 여집합 혹은 포함과 배제 혹은 적절하게 Tree로 만들어서 계층 순으로 색칠을 하는 방법 등을 떠올렸으나 전부 잘 안됐습니다. 그러다가 알게 된 성질이 있었습니다. 우선 i와 f[i]를 이은 그래프를 생각해봅시다. 대충 N = 6, f[i] = {2, 3, 1, 4, 5, 1} 이라고 한다면 그래프는 아래와 같이 생겼습니다.

그림을 좀 개떡같이 그렸긴한데, 어찌됐던 edge로 연결된 두 vertex의 색깔이 달라야한다는 점을 알 수 있습니다. 아직까지는 딱히 보이는게 없는데, 원래는 undirected graph이지만 i -> f[i]로 방향성을 부여해 그래프를 그려보면 명확한 사실을 하나 얻을 수 있습니다.

각 노드의 outdegree는 무조건 1개입니다. 그렇기 때문에 그래프들을 undirected graph 상에서의 component들로 분해해보면 반드시 아래와 같이 직선의 제일 끝에 cycle이 달려있는 형태를 가집니다.

왜 이런지 이해가 안간다면 outdegree가 반드시 1개임을 유념해서 생각해보면 될 것 같습니다.

그러면 이제 색칠을 cycle부터 해나가면 됩니다. 크기 i짜리 cycle을 K개의 색깔로 칠하는 경우의 수는 D[i] = K*(K-1)^(i-1)-D[i-1]입니다. 이는 크기 i짜리 cycle을 칠하는 경우의 수 = 크기 i짜리 직선을 칠하고, 1번째 node와 i번째 node의 색깔이 동일한 경우의 수라는 것으로부터 유도를 할 수 있습니다.

최종적으로, f[i]를 통해 만들어낸 그래프에서 찾아낸 모든 cycle의 길이를  이라고 할 때 총 경우의 수는

가 됩니다.

구현도 조금 까다롭고 graph coloring 문제를 떠올리는 것도 어려운 문제인 것 같습니다.

https://github.com/blisstoner/BOJ/blob/master/9521.cpp