SWEA 1949 [등산로 조성]

SW Expert Academy 등산로 조성 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

//SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다.

가장 긴 등산로를 만들 수 있는 경우를 찾는 문제입니다.

문제를 풀 때, 가장 간과할 수 있는점은 바로, "최대 K만큼 깎을 수 있다" 입니다.

즉, 1~K까지 깎을 수 있습니다.

따라서 다음 위치를 최대 K만큼 깎을 수 있을 때, 최소한으로 깎아준 뒤 DFS를 진행해 줬습니다.

(무작정 최대만큼 깎아놓으면, 깎인 좌표에서 다음 좌표로 못넘어갈수도 있습니다.)

//등산로조성
#include <iostream>
 
using namespace std;
 
int N;
int K;
int Mountain[8][8];
int Visited[8][8];
int highest;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
void DFS(int i, int j, int cnt, bool K_use);
bool boundary(int i, int j);
int length;
 
int main() {
    int T;
    cin >> T;
    for (int test_case = 0; test_case < T; test_case++) {
        cin >> N >> K;
        highest = 0;
        length = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> Mountain[i][j];
                Visited[i][j] = 0;
                if (highest < Mountain[i][j])
                    highest = Mountain[i][j];
            }
        }    
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (Mountain[i][j] == highest) {
                    DFS(i, j, 1, true);
                }
            }
        }
        cout << "#" << test_case +1 << " " <<length << endl;
    }
    return 0;
}
void DFS(int i, int j, int cnt, bool K_use) {
    Visited[i][j] = 1;
    for (int x = 0; x < 4; x++) {
        if (boundary(i + dx[x], j + dy[x])) {
            if (Mountain[i][j] > Mountain[i + dx[x]][j + dy[x]]) {
                DFS(i + dx[x], j + dy[x], cnt + 1, K_use);
            }
            else if (Mountain[i][j] <= Mountain[i + dx[x]][j + dy[x]] && K_use) {
                if (K > Mountain[i + dx[x]][j + dy[x]] - Mountain[i][j]) {
                    K_use = false;
                    int temp = Mountain[i + dx[x]][j + dy[x]];
                    Mountain[i + dx[x]][j + dy[x]] = Mountain[i][j] - 1;
                    DFS(i + dx[x], j + dy[x], cnt + 1, K_use);
                    Mountain[i + dx[x]][j + dy[x]] = temp;
                    K_use = true;
                }
            }
        }
    }
    Visited[i][j] = 0;
    if (length < cnt) {
        length = cnt;
    }
}
bool boundary(int i, int j) {
    if (i >= 0 && i < N && j >= 0 && j < N && Visited[i][j] == 0) {
        return true;
    }
    return false;
}