[BOJ] 15515번: Tap Titanz at Moloco

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

일단 인접한 색깔이 동일한 cell은 사실상 아무런 차이가 없으니 문제의 상황을 그래프로 간략하게 표현할 수 있습니다.

예를 들어 문제의 예시처럼 

BWB

WBW

WWW

를 생각해보면 이는 그래프로 아래와 같이 나타낼 수 있습니다.

(사실 색깔 정보는 저장할 필요가 없는게, 애초에 인접한 노드끼리는 색깔이 다름이 보장되기 때문입니다. 만약 색이 동일했다면 하나의 노드로 합쳐졌겠죠.) 이제 이 그래프에서 몇번의 tab을 해야 전체를 같은 색깔로 만들 수 있는지를 알아야하는데, 그 전에 하나의 노드를 반복해서 눌렀을 때 몇 번의 tab을 해야 전체를 같은 색깔로 만들 수 있는지 생각해보겠습니다.

하나의 노드를 반복해서 탭하는 과정을 생각해보면 마치 BFS와 같이 색이 퍼져나갈 것입니다. 그렇기에 BFS를 기준으로 그 노드로부터 가장 멀리 떨어진 노드까지의 거리가 하나의 노드를 반복해서 탭할 때 필요한 탭의 횟수입니다.

이제 다시 이 그래프에서 몇번의 tab을 해야 전체를 같은 색깔로 만들 수 있는지를 구해봅시다. 일단 정답부터 말하면, 모든 노드에 대해 그 노드를 반복해서 탭해서 전체를 같은 색깔로 만드는 횟수를 전부 계산한 후, 그것 중에서 가장 작은 것이 정답입니다. 이것이 성립하는 이유는 귀납적으로 증명이 가능합니다.

모든 노드에 대해 그 노드를 반복해서 탭해서 전체를 같은 색깔로 만드는 횟수 중에 가장 작은 값을 k라고 합시다.

i) k = 1일 때 정답 또한 1임은 자명합니다. 역 또한 자명하게 성립합니다.

ii) k = 1~n-1에 대해 전부 성립한다고 가정합시다.

iii) k = n일 때, 일단 정답은 반드시 n 이하입니다. 그런데 정답이 n보다 작을 경우 ii)번 과정에 의해 k = n일 수 없습니다.

그러므로 모든 노드에 대해 그 노드를 반복해서 탭해서 전체를 같은 색깔로 만드는 횟수 중에 가장 작은 값이 곧 정답임이 증명되었습니다.

저는 마치 좌표압축과 같이 따로 그래프를 만들어 풀이를 했으나 다른 사람의 코드를 보니 그렇지 않은 코드도 시간 내에 통과됐습니다.

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