BOJ 16957

16 Mar 2020 • ProblemSolving

체스판 위의 공

문제출처

문제 해석

  • 크기 RxC체스판의 각 칸에 공이 있을 때, 마지막 상태를 구하는 문제입니다.
  • 모든 공은 다음의 규칙을 따릅니다.
    1. 인접한 8방향에 적힌 모든 정수가 현재 칸의 수보다 크면 이동을 멈춥니다.
    2. 그 외의 경우에는 가장 작은 정수가 있는 칸으로 이동합니다.

설계(10)

  • 모든 공(R*C개)을 멈출 때 까지 탐색하는데 최악의 경우에 O((RxC)^2)의 시간복잡도가 나와서 시간초과가 날 것 입니다.
  • 여러번 중복탐색되는 것을 방지하기 위해서 여러가지 방법이 있겠지만 저는 union-find기법을 사용하였습니다.
  • 각 좌표를 기준으로 갈 수 있는 다음 좌표와 현재 좌표를 연결시켜줍니다.
  • 처음에는 모든 좌표에 대해서 연결해주는 방식으로 구현을 했지만 WA가 나왔습니다.
  • 특정한 경우에, 제대로 부모노드 연결이 제대로 안되는 경우가 있었습니다.
  • 이를 방지하고자, 체스판의 숫자를 오름차순으로 하여 union-find기법을 구현하였습니다.

구현(30)

코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 500

int map[MAXN][MAXN];
int parent[MAXN*MAXN];
int ans[MAXN][MAXN];
pair<int,int> coord[300001];
int R,C;
int find(int x){
    if (parent[x] < 0){
        return x;
    }
    return find(parent[x]);
}
bool is_range(int x, int y){
    return (x >= 0 && y >= 0 && x <R && y <C);
}
int dx[] = {-1,-1,-1,0,0,1,1,1};
int dy[] = {-1,0,1,-1,1,-1,0,1};
int max_num;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;
    memset(coord,-1,sizeof(coord));
    memset(parent,-1,sizeof(parent));
    for (int i = 0;i < R; i++){
        for (int j = 0 ;j < C; j++){
            cin >> map[i][j];
            coord[map[i][j]] = {i,j};
            max_num = max(max_num,map[i][j]);
        }
    }
    for (int i = 0 ;i <= max_num; i++){
        if (coord[i].first == -1) continue;
        int sx = coord[i].first;
        int sy = coord[i].second;
        int num = i;
        int x = -1;
        int y = -1;
        for (int k = 0;k< 8; k++){
            int nx = sx + dx[k];
            int ny = sy + dy[k];
            if (!is_range(nx,ny)) continue;
            if (map[nx][ny] < i){
                if (num > map[nx][ny]){
                    num = map[nx][ny];
                    x = nx;
                    y = ny;
                }
            }
        }
        // 이동가능한 경우
        if (x!=-1){
            int a = sx*C+sy;
            int b = x*C+y;
            a = find(a);
            b = find(b);
            if (a != b) parent[a] = b;
        }
    }
    for (int i = 0 ; i <R*C; i++){
        int x,y;
        if (parent[i] == -1){
            x = i / C;
            y = i % C;
        }
        else{
            x = parent[i]/C;
            y = parent[i]%C;
        }
        ans[x][y]++;
    }
    for (int i = 0;i <R; i++){
        for (int j = 0 ;j < C; j++){
            cout << ans[i][j] <<" ";
        }
        cout <<"\n";
    }
    return 0;
}
디버깅
제출결과
  • 68ms

마무리

  • union-find를 이용하는 문제였습니다. 단번에 해결법을 생각하지 못했지만, 해당 기법의 사용이 능숙해짐에 따라 이 문제에 응용할 수 있겠다는 생각이 들었습니다.
 BOJ

Related Posts