삼성 01949 - 등산로 조성

출처 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

 

고려사항

• 체크해줘야하고 다음 단계로 넘겨야할 인자들이 몇 개 있어서, bfs 보단 dfs 가 용이한 것 같다.
• 모든 방문하는 모든 지점에서, k만큼 높이를 낮췄는지에 대해서 useK 를 통해 관리하고,
  이전에 k만큼 낮췄다면, 이후 부터는 24 - 30 라인만 진행, 다음 방문할 지점이 현재 높이보다 낮은지만 비교,
  아직 k만큼 안 낮췄다면, 안 낮고 진행 가능 여부 판별 ( 30 - 35 라인 ),
  1 ~ k 까지 다음 지점을 낮춰가며 dfs 진행 ( 37 - 43 라인 )
• 코드를 조금 더 깔끔하게 할 수 있을 것 같다. ( 24 - 35 가 중복이다 )

 

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
 
int dy[4] = {-1, 1, 0 , 0};
int dx[4] = {0, 0, 1, -1};
int mount[8][8];
bool visit[8][8];
 
int t, n, k, ans;
 
void dfs(int y, int x, bool useK, int curHeight, int curLength){
    if(ans < curLength){
        ans = curLength;
    }
 
    int nextY, nextX;
    for(int i=0;i<4;++i){
        nextY = y + dy[i];
        nextX = x + dx[i];
 
        if(nextY>=0 && nextY<n && nextX>=0 && nextX<n && !visit[nextY][nextX]){
            if(useK){
                if(mount[nextY][nextX] < curHeight){
                    visit[nextY][nextX] = true;
                    dfs(nextY, nextX, true, mount[nextY][nextX], curLength+1);
                    visit[nextY][nextX] = false;
                }
            }else{
                if(mount[nextY][nextX] < curHeight){
                    visit[nextY][nextX] = true;
                    dfs(nextY, nextX, false, mount[nextY][nextX], curLength+1);
                    visit[nextY][nextX] = false;
                }
 
                for(int j=1;j<=k;++j){
                    if(mount[nextY][nextX]-j < curHeight){
                        visit[nextY][nextX] = true;
                        dfs(nextY, nextX, true, mount[nextY][nextX]-j, curLength+1);
                        visit[nextY][nextX] = false;
                    }
                }
            }
        }
    }
}
 
int main() {
    cin>>t;
    for(int i=1;i<=t;++i){
        ans = 1;
        int maxHeight = -1;
 
        memset(visit, 0, 64);
        cin>>n>>k;
        for(int p=0;p<n;++p){
            for(int q=0;q<n;++q){
                cin>>mount[p][q];
                maxHeight = max(maxHeight, mount[p][q]);
            }
        }
 
        for(int p=0;p<n;++p){
            for(int q=0;q<n;++q){
                if(mount[p][q] == maxHeight){
                    visit[p][q] = true;
                    dfs(p, q, false, mount[p][q], 1);
                    visit[p][q] = false;
                    for(int j=1;j<=k;++j){
                        //memset(visit, -1, 64);
                        visit[p][q] = true;
                        dfs(p, q, true, mount[p][q]-j, 1);
                        visit[p][q] = false;
                    }
                }
            }
        }
 
        cout<<"#"<<i<<" "<<ans<<"\n";
    }
    return 0;
}