1949 등산로 조성

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

다음 3가지 규칙에 따라 등산로를 만들 때 가장 긴 등산로의 길이를 구하는 문제이다.

1. 등산로는 가장 높은 봉우리에서 시작해야 한다.

2. 높은 봉우리에서 동서남북으로 점점 낮아져야 한다. 대각선은 연결할 수 없다.

3. 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 깎을 수 있다.

우선 가장 높은 봉우리들을 저장하고 DFS 백트래킹으로 각 지점들에서 시작하는 등산로들을 찾아 볼 수 있다. 그렇다면 3번 규칙은 어떻게 고려할 것인가? 경로를 탐색할 때 만약 현재 위치보다 새로운 위치의 높이가 더 낮다면 그냥 가면 된다. 현재 위치보다 새로운 위치가 더 클 때 최대 K만큼 깎아서 현재 위치보다 낮아지는지 확인한다. 최대한 길게 등산로를 조성하려면 새로운 위치를 현재 위치-1로 두고 다시 백트래킹할 때 원래 높이로 돌려놓으면 된다.

dfs(int x,int y,int len,int f) = 현재 위치가 (x,y), 현재 위치까지의 등산로의 길이가 len, f는 지형을 깎는 공사를 했는지의 여부

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int t,n,k,map[8][8],visit[8][8],ans;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 
void dfs(int x,int y,int len,int f)
{
    ans=max(ans,len);
    visit[x][y]=true;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx<0 || nx>=n || ny<0 || ny>=n || visit[nx][ny])
            continue;
        if(map[x][y]>map[nx][ny])
            dfs(nx,ny,len+1,f);
        else if(!f && map[x][y]>map[nx][ny]-k) 
        {
            int t=map[nx][ny];
            map[nx][ny]=map[x][y]-1;
            dfs(nx,ny,len+1,1);
            map[nx][ny]=t;
        }
    }
    visit[x][y]=false;
}
 
int main()
{
    scanf("%d",&t);
    for(int T=1;T<=t;T++)
    {
        scanf("%d %d",&n,&k);
        int m=0;
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
            scanf("%d",&map[i][j]),m=max(m,map[i][j]);
        vector<pair<int,int>> top;
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
            if(map[i][j]==m) top.push_back({i,j});
        int size=top.size();
        for(int i=0;i<size;i++)
            dfs(top[i].first,top[i].second,1,0);
        printf("#%d %d\n",T,ans);
        ans=0;
    }
    return 0;
}