[SW Expert Academy] 1949. 등산로 조성

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define p pair<int,int>
using namespace std;

int map[8][8];
int v[8][8]; // v is visit
int n,k;
int ans;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
vector<p> peak;

bool isEdge(int x, int y){
    if( x < 0 || x >= n || y < 0 || y >= n )
        return true;
    return false;
}

void dfs(int x, int y, int dept, int a_b){ // a_b is Available Break
    if(v[x][y])
        return ;
    
    int value = map[x][y];
    v[x][y] = 1;
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(isEdge(nx, ny))
            continue;
        
        if( value > map[nx][ny] ){
            dfs(nx,ny,dept+1,a_b);
        }
        else if(map[nx][ny] >= value && a_b == 1){ // Break 가능한 상태
            if(value > map[nx][ny] - k){
                int tmp = map[nx][ny];
                map[nx][ny] = value-1;
                dfs(nx,ny,dept+1,0);
                map[nx][ny] = tmp;
            }
        }
    } // end of for i
    v[x][y] = 0;
    ans = ans < dept ? dept : ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int TC;
    cin >> TC;
    for(int tc=1; tc<=TC; tc++){
        memset(map,0,sizeof(map));
        peak.clear();
        ans = -1;
        cin >> n >> k;
        
        int high_peak = -1;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cin >> map[i][j];
                if(high_peak < map[i][j])
                    high_peak = map[i][j];
            }
        }
        
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(high_peak == map[i][j])
                    peak.push_back(p(i,j));
            }
        }
        
        for(int i=0; i<peak.size(); i++){
            memset(v,0,sizeof(v));
            dfs(peak[i].first, peak[i].second, 1, 1);
        }
        
        cout << "#" << tc << " " << ans << endl ;
    }
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int map[9][9];
int visit[9][9];
int n,k;
int ans;

void dfs(int x, int y, int prev, int d, bool chk){ // d is depth
    ans = ans < d ? d : ans;
    visit[x][y] = 1;
    
    for(int i=0; i<4; i++){ // [1]
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        int now = prev;
        int next = map[nx][ny];
        
        // 다음 위치가 map범위 벗어나거나
        // 다음 위치를 이미 방문
        if( next == 0 || visit[nx][ny])
            continue;
        
        if( now > next )
            dfs(nx,ny,next, d+1, chk);
        
        if(!chk){
            for(int i=1; i<=k; i++)
                if ( now > next - i){
                    dfs(nx, ny, next-i, d+1, true);
                }
        }
    } // End of [1] Loop
    visit[x][y] = 0;
}

int main(){
    int tc = 10;;
    cin >> tc;
    
    for(int i=1; i<=tc; i++){
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        ans = 0;
        cin >> n >> k;
        
        int _max = -1;
        for(int a=1; a<=n; a++)
            for(int b=1; b<=n; b++){
                scanf("%d",&map[a][b]);
                _max = _max < map[a][b] ? map[a][b] : _max;
            }
        
        for(int a=1; a<=n; a++)
            for(int b=1; b<=n; b++)
                if( map[a][b] == _max)
                    dfs(a,b,map[a][b],1,false);
        
        printf("#%d %d\n",i,ans);
    }
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

int map[9][9];
int visit[9][9];
int n,k;
int ans;
bool chk;


void dfs(int x, int y, int prev, int d){ // d is depth
    if( visit[x][y] )
        return ;
    ans = ans < d ? d : ans;
    
    if( prev != 0 ) { // [0]
        visit[x][y] = 1;
        for(int i=0; i<4; i++){ // [1]
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            int now = prev;
            int next = map[nx][ny];
            
            if( now == 0 || next == 0 )
                continue;
            
            if( now > next )
                dfs(nx,ny,next, d+1);
            
            if(! chk){
                for(int i=1; i<=k; i++)
                    if ( now > next - i){
                        chk = true;
                        dfs(nx, ny, next-i, d+1);
                        chk = false;
                    }
            }
            
        } // End of [1] Loop
        visit[x][y] = 0;
    } // End of [0] If
}

int main(){
    int tc = 10;;
    cin >> tc;
    
    for(int i=1; i<=tc; i++){
        chk = false;
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        ans = 0;
        cin >> n >> k;
        
        int _max = -1;
        for(int a=1; a<=n; a++)
            for(int b=1; b<=n; b++){
                scanf("%d",&map[a][b]);
                _max = _max < map[a][b] ? map[a][b] : _max;
            }
        
        for(int a=1; a<=n; a++)
            for(int b=1; b<=n; b++){
                if( map[a][b] == _max)
                    dfs(a,b,map[a][b],1);
            }
            
                
        printf("#%d %d\n",i,ans);
    }
    return 0;
}