BOJ::16957 체스판 위의 공

시사점

이해(5)

설계, 손 코딩(11)

복잡도

구현(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)

좋은 코드

최적화