16957번 체스판 위의 공

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

# 시간초과 # 복습 # 구현 # 생각 # 아이디어 # 유니온 # 파인드 # Find # 경로 # 압축 # Union

처음 구현했을 때, 시간 초과가 발생했다.

이 문제의 핵심은 경로 압축(Path Compression)이다.

간단하게 말하자면, 

30에서 계속 최솟값을 통해 가다가 2로 도착하였다면,

또 다른 숫자인 50에서 출발하여 최솟값을 통해 계속 진행하다가 30을 만나면 더이상 진행할 필요가 없다는 뜻이다.

즉, 30에서 이미 2로 도착하였기 때문이다.

이 문제는 Union-Find에서 Find를 활용하는 문제이다.

예제 1로 설명을 하겠다.

우선 예제 1을

1 3 4

5 6 7

8 9 2

이렇게 접근하지 말고, 아래와 같이 접근을 해보자.

숫자 내용 자체를 바꾸자는 뜻이 아니라,

1이 있는 자리 (0, 0)에 0번을 부여

3이 있는 자리 (0, 1)에 1번을 부여

4가 있는 자리 (0, 2)에 2번을 부여

.

.

.

라는 의미이다.

번호를 부여할 때는 현재 좌표(r, c)에 대하여 r*C + c로 하면 된다.

C는 입력값(열의 길이)

그런 다음 모든 좌표에 대하여 인접한 좌표들(자신 포함)의 최솟값을 찾는 과정을 한 번만 실행해보자.

그리고 화살표를 표시해보자. 

작은 값 ← 큰 값

p[큰 값] = 작은 값

예를 들어, 1의 인접한 주변에는 3, 5, 6, 1(자신)이 있고, 최솟값은 1이다. 즉, 자기 자신이다. 

1 ← 1 

이것을 부여한 번호로 표시하면, [0] ← [0]이다.

p[0] = 0;

3의 주변에는 1이 최솟값이고, 1 ← 3이다.

부여한 번호로 표시하면, [0] ← [1]이다.

p[1] = 0;

.

.

.

계속 진행하면, 아래와 같은 결과가 나온다.

위의 그림을 보면 바로 생각이 떠오를 것이다. Union-Find

한 번만 진행한 다음, Find 함수를 통해 Find 값을 인덱스로 하는 배열인 ans의 값을 1을 증가시키면 된다.

++ans[Find(i*C + j)];

다시 말하면,

[0], [1], [2], [3], [4], [6]을 진행하면, Find는 0을 return할 것이고, 이에 대한 ++ans[0];을 수행하여 최종적으로 6이 나올 것이다.

시간 초과

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 505
#define INF 2e9
 
int m[Max][Max], ans[Max][Max], R, C;
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
vector<pair<int, int> > v;
 
// 인접한 숫자들과의 비교((r, c) 위치에 있는 숫자가 제일 작은지)
bool isSmallest(int r, int c)
{
    for (int i = 0; i < 8; i++) {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= R || x < 0 || x >= C) {
            continue;
        }
 
        if (m[r][c] > m[y][x]) {
            return false;
        }
    }
 
    return true;
}
 
void print()
{
    printf("\n===================\n");
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
 
    printf("\n");
}
 
void simulation()
{
    while (true)
    {
        bool stop = true;
 
        for (auto &i : v) {
 
            // 현재 위치에 있는 숫자가 가장 작으면
            if (isSmallest(i.first, i.second)) {
                continue;
            }
 
            // 아래 실행 여부
            stop = false;
 
            int r = i.first, c = i.second;
            int y = 0, x = 0;
 
            // 이동해야한다면 가장 작은 숫자가 있는 칸으로 이동
            int Min = INF, diry = 0, dirx = 0;
            for (int d = 0; d < 8; d++) {
                y = r + dy[d];
                x = c + dx[d];
 
                if (y < 0 || y >= R || x < 0 || x >= C) {
                    continue;
                }
 
                // 이동 방향 저장
                // dy, dx임을 주의
                if (Min > m[y][x]) {
                    Min = m[y][x];
                    diry = dy[d];
                    dirx = dx[d];
                }
            }
 
            y = r + diry;
            x = c + dirx;
 
            ++ans[y][x]; // 이동할 칸
            --ans[r][c]; // 원래 위치 칸
            
            i.first = y; // 저장
            i.second = x; // 저장
        }
 
        if (stop) {
            break;
        }
    }
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
            v.push_back({ i, j });
            ans[i][j] = 1;
        }
    }
 
    simulation();
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
 
    return 0;
}

정답

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 505
#define INF 2e9
 
int m[Max][Max], p[Max * Max], ans[Max * Max], R, C;
int dy[9] = { 0, 1, 1, 1, 0, -1, -1, -1, 0 }; // 자신 포함(0, 0)
int dx[9] = { 1, 1, 0, -1, -1, -1, 0, 1, 0 }; // 자신 포함
 
int Find(int x)
{
    if (x == p[x]) return x;
    return p[x] = Find(p[x]);
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d", &R, &C);
 
    int idx = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
        }
    }
 
    // 우선 한 번만 진행
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            int Min = INF, ey = 0, ex = 0;
 
            for (int k = 0; k < 9; k++) {
                int y = i + dy[k];
                int x = j + dx[k];
 
                if (y < 0 || y >= R || x < 0 | x >= C) {
                    continue;
                }
 
                // 가장 작은 값을 찾는다.
                if (Min > m[y][x]) {
                    Min = m[y][x];
                    ey = y;
                    ex = x;
                }
            }
 
            // 부모 표시
            p[i*C + j] = ey*C + ex;
        }
    }
 
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            ++ans[Find(i*C + j)];
        }
    }
 
    for (int i = 0; i<R; i++) {
        for (int j = 0; j<C; j++) {
            printf("%d ", ans[i*C + j]);
        }
        printf("\n");
    }
 
    return 0;
}