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

 

16957번: 체스판 위의 공

크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙

www.acmicpc.net

 

 

[난이도] Gold4
[유형] DP

[풀이]
union-find의 find와 비슷한 개념을 이용하면 시간초과에 걸리지 않고 해결할 수 있습니다.
pair<int,int> dest[501][501] 를 선언하여 dest[y][x] 에는 y,x에서 출발 했을 때 최종으로
도착하는 점 {dest_y,dest_x}를 저장해 주었습니다.
board[y][x]의 수가 높은 수부터 탐색을 해주어야 하며
탐색 도중 다음 가야하는 점의 dest 값이 이미 구해져 있다면 이 값을 그대로 이용하며 탐색을 종료하면
시간 초과를 피할 수 있습니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<pair<int,pair<int,int>>> v;
int R,C,board[501][501],cnt[501][501];
int dy[8] = {-1,1,0,0,1,-1,1,-1};
int dx[8] = {0,0,1,-1,1,-1,-1,1};
pair<int,int> dest[501][501];
pair<int,int> sol(int y,int x){
    int minV=4e5,my,mx;
    for(int i=0;i<8;i++){
        int ny=y+dy[i], nx=x+dx[i];
        if(ny<1||nx<1||ny>R||nx>C) continue;
        if(board[ny][nx] < minV){
            minV=board[ny][nx];
            my=ny;
            mx=nx;
        }
    }
    if(board[y][x] > minV){
        if(dest[my][mx].first!=0) return dest[y][x] = dest[my][mx];
        return dest[y][x] = sol(my,mx);
    }
    return dest[y][x]={y,x};
}
int main(){
    scanf("%d%d",&R,&C);
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++){
            scanf("%d",&board[i][j]);
            v.push_back({board[i][j],{i,j}});
        }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    for(auto p : v){
        auto [y,x] = p.second;
        if(dest[y][x].first==0) sol(y,x);
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            auto [y,x] = dest[i][j];
            cnt[y][x]++;
        }
    }
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++){
            printf("%d ",cnt[i][j]);
        }
        puts("");
    }   
}


https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/16957.cpp

+ Recent posts