문제 링크
- http://icpc.me/2452
문제 출처
- 2011 KOI 중4/고4
사용 알고리즘
- BFS
풀이
어떤 돌 하나만 반복해서 선택해도 최적해가 나온다는 것이 증명되어있습니다. 이것을 이용해 풀이를 생각해봅시다.
인접하면서 같은 색깔인 돌은 선택하는 횟수가 같기 때문에 묶어서 생각해줄 수 있습니다. 인접하면서 같은 색깔인 돌들을 하나의 정점으로 잡고, 인접한 영역끼리 간선으로 이어준 그래프를 만들어줄 수 있습니다.
어떤 돌 하나만 반복해서 선택해도 되기 때문에, 각 정점별로 가장 멀리 떨어진 점의 거리를 구한 다음 최솟값을 구해주면 답이 된다는 사실을 알 수 있습니다.
시간 초과가 날 수 있기 때문에 적당한 커팅을 해주면 AC를 받을 수 있습니다.