BOJ
BOJ::16957 체스판 위의 공
BOJ Gold 4
BOJ::16957 체스판 위의 공
- Link : BOJ::16957
- Level : Gold 4
- tag : dfs, dynamic programming, graph theory
시사점
- swea에 있는 핀볼 문제와 비슷합니다.
- 즉, 누군가 이미 지나갔던 경로라면, 해당 경로의 끝점에 있는 지점과의 처리만 해주고 return하는 형식의 dfs함수를 사용합니다.
이해(5)
- R * C 체스판이 주어집니다.
- 초기에 모든 정점에 공이 하나씩 올려져 있습니다.
- 이 공들은 주변 8개의 정점 혹은 자기 자신 중 가장 작은 값을 가지는 정점으로 흘러갑니다.
- 쉽게 상상하자면, 높낮이가 다른 움푹 패인 여러 구덩이가 있다고 생각할 수 있습니다.
- 최종적으로 모든 공이 더이상 움직이지 않을때, 종료하고 보드의 상태를 출력합니다.
설계, 손 코딩(11)
- 손으로 중심이 되는 코드를 구현합니다.
- simulation time이 10^3 이상이라면, naive하게는 TLE가 예상됩니다.
- 따라서, 조금 더 greedy한 방법을 떠올려 봐야 합니다.
- 여러 개의 움푹 패인 구덩이가 있는 보드로 생각할 수 있습니다.
- 그리고, 모든 점에 공을 올려놓는다면 각 공은 어디로 갈까요?
- 뱅글 뱅글 돌다가 결국, 주변에 있는 지점 중 가장 높이가 낮은 지점으로 흘러가고,
- 해당 지점에서 정지하게 됩니다.
- 그렇다면, 이미 어떤 공이 지나가면서 흔적을 남긴 길에 내가 지금 공을 들고 올라온 경우,
- 굳이 끝까지 또 따라가 볼 필요가 없습니다.
- 도착점만 알고 있다면 말입니다.
- 따라서, pair<int,int> end_point[N][N]; 이라는 배열을 사용하여 해당 역할을 해주게 하면, O(NM)에 풀 수 있습니다.
복잡도
- T : O(NM)
구현(8)
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_abck
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int MAXNM = 500;
const int dx[]={-1, -1, -1, 0, 0, 1, 1, 1}, dy[]={-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
int a[MAXNM][MAXNM];
int balls[MAXNM][MAXNM];
pair<int,int> endp_of[MAXNM][MAXNM];
bool over(int x, int y){return (x<0 || y<0 || x>=n || y>=m);}
void input(){
cin >> n >> m;
rep(i, 0, n) rep(j, 0, m) cin >> a[i][j], balls[i][j] = 1, endp_of[i][j] = {-1, -1};
}
int ex, ey;
void dfs(int x, int y, int depth){
if(endp_of[x][y].first != -1){
ex = endp_of[x][y].first, ey = endp_of[x][y].second;
balls[ex][ey] += depth;
return;
}
int minIdx = -1, minValue = a[x][y];
rep(i, 0, 8){
int nx = x+dx[i], ny = y+dy[i];
if(over(nx, ny)) continue;
if(a[nx][ny] < minValue){
minIdx = i;
minValue = a[nx][ny];
}
}
// end point
if(minIdx == -1){
ex = x, ey = y;
balls[x][y] += depth;
}else{
dfs(x + dx[minIdx], y + dy[minIdx], depth+1);
balls[x][y] = 0;
}
endp_of[x][y] = {ex, ey};
}
void process(){
input();
rep(i, 0, n){
rep(j, 0, m){
ex = -1, ey = -1;
if(balls[i][j])
dfs(i, j, 0);
}
}
}
void PRINT(){
rep(i, 0, n){
rep(j, 0, m){
cout << balls[i][j] << " ";
}cout << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
process();
PRINT();
return 0;
}
디버깅(3)
- 한가지 실수한 점이 있습니다.
- (3m) : dfs 함수에 들어가자마자 해당 정점이 끝점인지 확인합니다.
- 끝점인 경우, 종점에 depth를 더해줍니다.
- 하지만 더해주기 전에 balls[x][y] = 0;으로 초기화 해주었습니다.
- 이 경우 x == ex, y == ey 인 경우 반례가 발생합니다.
- 따라서, 삭제처리하였습니다.
- (3m) : dfs 함수에 들어가자마자 해당 정점이 끝점인지 확인합니다.