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
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold4] 16964 : DFS 스페셜 저지 (C++) (0) | 2021.12.18 |
|---|---|
| [BOJ/백준][Gold3] 15711 : 환상의 짝 (C++) (0) | 2021.11.09 |
| [BOJ/백준][Gold3] 1943 : 동전 분배 (C++) (0) | 2021.11.09 |
| [BOJ/백준][Gold1] 12837 : 가계부 (Hard) (C++) (0) | 2021.11.09 |
| [BOJ/백준][Gold4] 1757 : 달려달려 (C++) (0) | 2021.11.09 |