[SWEA 1949] 등산로 조성

문제풀이

dfs로 완전탐색하여 풀이하였다.

문제의 핵심은 가장 높은곳에서 시작하는 것과 공사를 오직 1번만 진행할 수 있다는 것이다.

input을 받을때 가장 큰 높이를 저장한 뒤 값을 참조하여 탐색한다. 처음에는 좌표를 저장하여 그 좌표에서만 시작하려 했는데 큰 차이는 없을것 같아 높이를 참조하여 시작점을 찾았다.

1. 내리막길인 경우 dfs로 길이를 구해주면 되고

2. 오르막길이고 공사를 진행한 적이 없다면 최소한의 높이를 깎은 뒤 내리막 길이 되면 dfs로 길이를 구해주면 된다. 이때 최대값 k만큼의 높이를 깎는다면 다음 좌표로 이동할 수 없을 수도 있으니 주의하자.

이후 dfs를 통해 등산로 길이의 최대값을 출력해주는 문제이다.

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 8
#define endl "\n"
using namespace std;
int n, k, maxHeight, ans;
int map[MAX][MAX];
bool visit[MAX][MAX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
 
// 모의 SW 역량테스트 1949 등산로 조성 
// 가장 높은곳에서 시작
// 높은 지형 -> 낮은 지형 상/하/좌/우 이동 
// 최대 k만큼 지형을 깎는다. (오직 한 지점에만 가능) 
 
// y좌표, x좌표, 현재까지 길이, 공사 여부 
void dfs(int y, int x, int cnt, bool isCutting) {
    ans = max(ans, cnt);
    
    for (int i=0; i<4; i++) {
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        // map범위를 초과하거나 이미 방문한 지점이면 continue 
        if (ny<0 || nx<0 || ny>=n || nx>=n || visit[ny][nx]) continue;
        
        // 내리막길 
        if (map[y][x] > map[ny][nx]) {
            visit[ny][nx]=1;
            dfs(ny, nx, cnt+1, isCutting);
            visit[ny][nx]=0;
        } 
        
        // 오르막길 && 공사진행 X 
        else if (map[y][x] <= map[ny][nx] && !isCutting) {
            
            // 최소한으로 높이를 깎는다. 
            for (int d=1; d<=k; d++) {
                isCutting=1;
                map[ny][nx] -= d;
                
                // 내리막길이 되면 
                if (map[y][x] > map[ny][nx]) {
                    visit[ny][nx]=1;
                    dfs(ny, nx, cnt+1, isCutting);
                    visit[ny][nx]=0;
                }
                map[ny][nx] += d;
                isCutting=0;
            }    
        }
    }
}
 
void solve() {
    for (int y=0; y<n; y++) {
        for (int x=0; x<n; x++) {
            if (map[y][x] == maxHeight)    {
                visit[y][x]=1;
                dfs(y, x, 1, 0);
                visit[y][x]=0;
            }
        }
    }
}
 
void init() {
    int tc;
    cin>>tc;
    for (int t=1; t<=tc; t++) {
        cin>>n>>k;
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        ans = 1;
        maxHeight = 0;
        
        for (int y=0; y<n; y++) {
            for (int x=0; x<n; x++) {
                cin>>map[y][x];
                maxHeight = max(maxHeight, map[y][x]);    
            }
        }
        
        solve();
        
        cout<<"#"<<t<<" "<<ans<<endl;    
    }
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    init();
    return 0;
}