BOJ 2452: 그리드 게임

Link

• https://www.acmicpc.net/problem/2452

• KOI 2011 전국본선 중/고등부 4번

Tag

• bfs

Time Complexity

• $O(N^{2}M^{2})$

흰색/검은색 돌로 구성된 $N*M$ 격자가 주어진다. 어떤 돌을 선택해 뒤집으면 같은 색으로 연결된 컴포넌트들이 전부 뒤집힌다. 전체 격자를 같은 색으로 바꾸기 위해 필요한 최소한의 뒤집기 횟수를 구해야 한다.

 

가장 중요한 관찰은, '처음 뒤집은 돌을 계속 뒤집어도 된다'는 것이다. 따라서 $N*M$개의 돌을 모두 시도해 보면서, 그 돌만 눌렀을때 총 몇번 뒤집어야 하는지 계산하면 된다.

 

인접한 돌들끼리 간선을 연결하고, 같은 색끼리는 0, 색이 다르면 1의 가중치를 가지는 그래프를 생각해 보자. 이때 $(sx, sy)$의 돌을 계속 뒤집으면 $(sx, sy)$과 최단거리가 가장 먼 돌이 마지막에 연결될 것이다. 즉 가장 큰 최단거리만큼 뒤집어야 함을 할 수 있다.

 

따라서 모든 후보를 시도하면서 최단거리를 계산해주면 된다. 나는 가중치가 0, 1 이란 점을 이용해 0-1 BFS로 탐색했다.

 

최종 시간복잡도는 $O(N^{2}M^{2})$가 된다. deque가 느려서 그런지 같은 정점 묶어주기 등 커팅을 조금 해야 AC를 받을 수 있다.

Code