[SWEA 1949] 등산로 조성 (C++)

문제 링크: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

SW Expert Academy

1. 주의할 점

- 깍고 다음칸으로 가는 경우, 현재 높이에서 1만큼만 작게 깍았다고 가정한다

 

2. 구현

- 등산로에 대한 정보를 Arr[][] 배열에 받고, 그 중에서 가장 높은 높이를 저장한다

- 전역변수들을 초기화한다

- Arr[][] 배열중에서 가장 높은 높이인 경우, DFS() 함수를 수행하여 조건에 따라 이동한다

- 이때, Height 변수도 넘겨서 Arr[][] 배열을 직접 수정하지 않도록 한다(깍을 경우). 또한, DFS() 함수의 시작과 끝부분에 방문에 대한 처리를 수행한다

#include <iostream>
#include <algorithm>
using namespace std;
int num,result,dig;
int arr[8][8];
bool check[8][8];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};

int dfs(int y, int x, int height, bool digged){
    check[y][x]=true;
    int cnt = 0;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=0 && ny>=0 && nx<num && ny<num && !check[ny][nx]){
            if(arr[ny][nx]<height){
                cnt=max(cnt,dfs(ny,nx,arr[ny][nx],digged));
            }
            else{
                if(!digged && arr[ny][nx]-dig<height){
                    cnt=max(cnt,dfs(ny,nx,height-1,true));
                }
            }
        }
    }
    check[y][x]=false;
    return cnt+1;
}

int main() {
    int test,maxi;
    cin>>test;
    for(int t=1;t<=test;t++){
        cin>>num>>dig;
        result=0;
        maxi=0;
        for(int i=0;i<num;i++)
            for(int j=0;j<num;j++){
                cin>>arr[i][j];
                check[i][j]=false;
                maxi = max(maxi, arr[i][j]);
            }
        for(int i=0;i<num;i++)
            for(int j=0;j<num;j++){
                if(arr[i][j]==maxi){
                    int tmp = dfs(i,j,arr[i][j],false);
                    result = max(result, tmp);
                }
            }
        cout<<"#"<<t<<" "<<result<<'\n';
    }
    
    return 0;
}