2452번: 그리드 게임

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


$O(n^4)$

같은 색끼리 노드를 형성하고 인접한 노드끼리 연결해서 그래프를 만들 수 있다.
답으로 임의의 노드에 대해 해당 노드로부터 가장 멀리 떨어진 거리가 최소가 되는 거리를 출력하면 된다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
vector<int> adj[10001];
int s[100][100], c[100][100], m, n, cnt, pcnt, r = 1e9;
pair<int, int> p[40000];
void ff(int x, int y, int ss, int cc) {
    if (x < 0 || y < 0 || x >= m || y >= n || s[x][y] ^ ss || c[x][y]) return;
    c[x][y] = cc;
    for (int i = 0; i < 4; i++) ff(x + fx[i], y + fy[i], ss, cc);
}
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", &s[i][j]);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (!c[i][j]) ff(i, j, s[i][j], ++cnt);
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) for (int k = 0; k < 4; k++) {
        int tx = i + fx[k], ty = j + fy[k];
        if (tx >= 0 && ty >= 0 && tx < m && ty < n && s[i][j] ^ s[tx][ty]) p[pcnt++] = { c[i][j],c[tx][ty] };
    }
    sort(p, p + pcnt);
    pcnt = unique(p, p + pcnt) - p;
    while (pcnt--) adj[p[pcnt].first].push_back(p[pcnt].second);
    for (int i = 1; i <= cnt; i++) {
        int q[10000], ck[10001] = { 0, }, h = 0, t = 1;
        ck[i] = 1; q[0] = i;
        while (h^t && ck[q[h]]<r) {
            for (auto it : adj[q[h]]) if (!ck[it]) {
                ck[it] = ck[q[h]] + 1;
                q[t++] = it;
            }
            h++;
        }
        r = ck[q[t - 1]];
    }
    printf("%d", r - 1);
    return 0;
}

그러나 위 소스는 대회 환경에서 시간초과로 만점을 받지 못할 것이다.
만점을 받기 위해선 적절한 컷팅이 필요한다.

1. 중간 번호 노드부터 탐색 - 보통 중간에 위치하면 최소 거리가 되기 때문
2. 탐색 노드 개수 제한 - 1번 탐색 방법에 따라 모퉁이에서 답이 나올 가능성이 거의 없음
3. bfs 탐색시 현재까지 구한 답보다 큰 거리를 탐색하면 무시하기