제 5회 kriiicon YZ(Young Zebra)

https://oj.uz/problem/view/KRIII5_YZ

\(1\leq{N,M}\leq{400}\)

N x M 의 격자가 주어진다. 격자의 각 칸은 'B' 또는 'W' 이다.

이 격자를 상하좌우대각선으로 무한히 이어붙였을때 무늬가 나타날 것이다. 여기에는 같은 색끼리 상하좌우로

붙어있기도하고 혼자있기도 할텐데 이 같이 붙어있는 수를 각 칸마다 구하는 문제이다. 무한히 많은 같은색 칸이

붙게 되는 칸은 -1 을 출력한다.

예를 들어

이 경우에는 답이

2 2 -1

-1 -1 -1

이 된다.

흰 칸들은 모두 무한히 이어지며, 검은칸들은 각각 두개씩 붙어있기 때문이다.

그럼 이문제를 어떻게 풀까?

dfs로도 풀 수가 있겠지만 구현도 쉽고, 예외처리해줄것도 적어 깔끔한 유니온 파인드로 풀어보자.

모든 칸들에 대해 상하좌우와 merge해주는데 range 를 벗어났을 경우 모듈러 연산을 통해 왼쪽 끝의 왼쪽은 오른쪽끝이며

오른쪽끝의 오른쪽은 왼쪽끝이라고 보면서 해준다. 이렇게 하면 각 칸이 몇개의 칸들과 모여있는지 계산할 수 있지만

유한한 경우만이며 무한인지 판별할 수는 없다. 그렇다면 무한과 유한을 구분하려면 어떻게 해야할까?

우선 N x M 의 격자를 상하좌우대각선에 그대로 복사하여 3 x 3 의 큰 격자를 만들고

모든 칸에 대해 merge를 다 해준다. 이 때 3x3 이라고 안심하여

range 에서 벗어나는 경우를 모듈러로 처리 안해주면 안되는데 반례가 이것이다.

빨간선부분이 'B'라고 생각했을 때 가운데 격자에서 맨 왼쪽 선을 보면 실제로 무한히 격자를 이어붙이면 결과적으로

다른 선 두개와 연결되는데 이 그림에서 range 넘어가는 부분을 봐주지 않으면 하나와 연결된다고 판단하기 때문이다.

이 때 가운데의 어떤 한 칸 (i+N,j+M) 가 있을 때 

이 칸에서 상하좌우에 있는 격자 중 하나라도 같은 위치에 갈 수 있다면 무한이다. 즉, 

(i+N, j+M) 이 (i+N,j), (i+N, j+2M), (i, j+M), (i+2N, j+M) 이렇게 8개의 칸 중

아무 하나와 같은 집합에 속해있다면 무한이라고 판단할 수 있다.

....가 아니라 중요한건 대각선에 있는 (i, j), (i, j+2M), (i+2N, j), (i+2N, j+2M) 네개도 봐줘야 하는데 그 반례가 아래에 있다.

이 경우는 빨간선으로 표시한 부분이 'B'라고 생각해봤을 때 이 칸들은 모두 무한인데도 불구하고

대각선하고만 이어지기 때문에 대각선도 봐줘야 한다는 것을 알 수 있다.

그럼 이제 가운데 격자의 모든 칸에 대해

무한이면 -1, 유한이면 그 칸이 속하는 집합의 원소수를 출력하면 된다.

시간 복잡도는 \(O(MN)\) 인데 상수를 생각해보면 사실은 \(O(36MN)\) 이다. 왜냐면 3배로 칸을 늘렸고 상하좌우4개씩

봐주기 때문이다. 그런데 이걸 계산해보면 최악의경우 5760000 이기 때문에 충분하므로 굳이 감안할 필요는 없을 것같다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int N,M;
char pane[403][403];
char pane2[1203][1203];
int parent[1440003];
int size[1440003];
int calcId(int i, int j){
    return i*3*M + j;
}
int find(int p){
    if(p==parent[p]) return p;
    return parent[p] = find(parent[p]);
}
void merge(int a, int b){
    a = find(a), b = find(b);
    if(a==b) return;
    parent[a] = b;
    size[b] += size[a];
}
bool inRange(int i, int j){
    return 0 <= i && i < 3*N && 0 <= j && j < 3*M;
}
 
int main() {
    for(int i = 0 ; i < 1440003; i++) parent[i] = i, size[i] = 1;
    scanf("%d%d", &N, &M);
    for(int i = 0 ; i < N ; i++){
        scanf("%s",pane[i]);
    }
 
    for(int i = 0 ; i < 3*N; i++){
        for(int j = 0 ; j < 3*M; j++){
            pane2[i][j] = pane[i%N][j%M];
        }
    }
 
    for(int i = 0 ; i < 3*N; i++){
        for(int j = 0 ; j < 3*M; j++){
            for(int k = 0 ; k < 4; k++){
                int ni = (i+"1201"[k]-'1'+3*N)%(3*N);
                int nj = (j+"2110"[k]-'1'+3*M)%(3*M);
                if(!inRange(ni, nj) || pane2[i][j] != pane2[ni][nj]) continue;
                merge(calcId(i, j), calcId(ni, nj));
            }
        }
    }
    for(int i = N; i < 2*N; i++){
        for(int j = M; j < 2*M; j++){
            for(int k = 0 ; k < 8; k++){
                int ni = i+("12010202"[k]-'1')*N;
                int nj = j+("21100022"[k]-'1')*M;
                if(find( calcId(i, j) ) == find( calcId(ni, nj) )) size[find(calcId(i, j))] = -1; 
            }
        }
    }
 
    for(int i = N; i < 2*N; i++){
        for(int j = M; j < 2*M; j++){
            printf("%d ",size[find(calcId(i, j))]);
        }
        printf("\n");
    }
    return 0;
}