1949 등산로 조성

SWEA::1949 등산로 조성

1. dfs로 모든 경우에 대해 탐색

2. 탐색할때 k만큼 깍는 작업을 했는지 안했는지에 따라 분류

3. k만큼 깍는 작업을 하고 넘어 왔을경우, 이전 상태를 알려주는 pre 매개변수를 통해 넘어온 지점이 얼마로 깍여 왔는지에 대해 알 수 있고 pre 변수로 다음 지점과 비교하여 탐색.

4. 최대값 찾는다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
int t, n, k, res;
int map[9][9];
bool visited[9][9];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void dfs(int x, int y, int cnt, int pre, bool flag) {
    visited[x][y] = true;
    if (res < cnt) res = cnt;
 
    for (int i = 0; i < 4; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
 
        //방문했거나 범위 벗어나면 continue
        if (ax == 0 || ay == 0 || ax == n + 1 || ay == n + 1 || visited[ax][ay]) continue;
 
        //깍기 사용x
        if (flag) {
            //내리막길인 경우
            if (map[x][y] > map[ax][ay]) {
                dfs(ax, ay, cnt + 1, map[ax][ay], true);
            }
            //내리막길이 아닌 경우
            else {
                if (map[x][y] > map[ax][ay] - k) {
                    dfs(ax, ay, cnt + 1, map[x][y] - 1, false);
                }
            }
        }
        //이미 깍기 사용
        else {
            if (pre > map[ax][ay]) {
                dfs(ax, ay, cnt + 1, map[ax][ay], false);
            }
        }
    }
    visited[x][y] = false;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++) {
 
        cin >> n >> k;
        res = 0;
        int max_val=0;
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> map[i][j];
                max_val = max(map[i][j], max_val);
            }
        }
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (map[i][j] == max_val) {
                    //탐색
                    dfs(i, j, 1, map[i][j], true);
                }
            }
        }
 
        cout << "#" << tc << " " << res << endl;
 
    }
}