[C++] 삼성 1949. [모의 SW 역량테스트] 등산로 조성

#include <iostream>
#include <vector>
 
using namespace std;
 
int arr[8][8];
int visit[8][8];
 
int dir[][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int max_dist = 0;
int N;
int K;
 
void solution(int x, int y, bool k, int dist) {
    if (x < 0 || y < 0 || x >= N || y >= N)
        return;
 
    for (int i = 0; i < 4; i++) {
        int next_x = x + dir[i][0];
        int next_y = y + dir[i][1];
 
        if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)
            continue;
 
        if (visit[next_x][next_y] == 1)
            continue;
 
        if (arr[x][y] > arr[next_x][next_y]){
            visit[x][y] = 1;
            solution(next_x, next_y, k, dist+1);
            visit[x][y] = 0;
        }
        else if (k == false) {
            for (int j = 1; j <= K; j++) {
                arr[next_x][next_y] -= j;
                if (arr[x][y] > arr[next_x][next_y]) {
                    visit[x][y] = 1;
                    solution(next_x, next_y, true, dist+1);
                    visit[x][y] = 0;
                }
                arr[next_x][next_y] += j;
            }
        }
    }
 
    if (max_dist < dist)
        max_dist = dist;
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        max_dist = 0;
        int max_top = 0;
 
        cin >> N >> K;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> arr[i][j];
                if (max_top < arr[i][j])
                    max_top = arr[i][j];
            }
        }
 
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == max_top)
                    solution(i, j, false, 1);
            }
        }
        
        cout << "#" << t << " " << max_dist << endl;
    }
 
    return 0;
}