[C++] SWEA 1949 등산로 조성

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

가장 긴 등산로를 만드는 문제로 시작점은 가장 높은 봉우리에서 시작한다.

입력을 받을 때 가장 높은 숫자를 highest 변수에 저장하고

완전 탐색을 돌리는듯 하면서 값이 highest일 때만 dfs를 돌려서 탐색한다.

// 값 저장
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        cin >> arr[i][j];
        highest = max(highest, arr[i][j]);
    }
}

A->B 까지 가는 등산로는 A->C->D->B로 돌아서 가는 식의 등산로로 표현할 수도 있기 때문에

A->까지 최단 경로로 등산로가 완성되었다고 하더라도 다른 루트로 돌아서 가는 형태를 고려하는 백트래킹 방식의 탐색을 해야한다.

dfs를 돌리기 전에 방문 체크를 해주고 dfs가 끝난 시점에서 방문 해제를 해줘야 한다.

visited[i][j] = true;
dfs(cur);
visited[i][j] = false;

문제에서 특이한 조건이 하나 있는데, [긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.]

이 조건에 따라서 등산로를 만들 수 없는 탐색 지역이 있으면 등산로 공사를 통해서 진행을 해주는 코드를 넣어야 한다.

현재 노드를 cur로 하고 다음 노드를 nxt라고 했을때,

(cur의 높이) <= (nxt의 높이) 인 경우

(cur의 높이) > (nxt의 높이) - (최대 공사 가능 깊이) 가 성립하는 경우에 탐색이 가능하다고 할 수 있다.

다만, 이 때 주의할 점은 최대한 길게 등산로를 만들어야 하기 때문에 (cur의 높이)에서 -1 만 해주도록 한다.

if (!cur.chk && cur.h > nxt.h - K) {
    nxt.chk = true; // 공사 체크
    nxt.h = cur.h - 1; // 1만큼만 빼기
    flag = true;
}

dfs 백트래킹을 돌릴 때 저장할 값들은 구조체에 좌표, 높이, 등산로길이, 공사여부를 담았다.

struct point {
    int x, y; // 좌표
    int h;    // 높이
    int len;  // 등산로 길이
    bool chk; // 공사여부
};

// SWEA_1949 등산로 조성
#include <iostream>
#include <vector>
 
using namespace std;
 
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
 
vector<vector<int> > arr;
vector<vector<bool> > visited;
int N, K; // 한변의 길이, 최대 공사 가능 깊이
int highest; // 가장 높은 등산로 높이
int result;
 
int max(int a, int b) {
    return a > b ? a : b;
}
 
struct point {
    int x, y; // 좌표
    int h;    // 높이
    int len;  // 등산로 길이
    bool chk; // 공사여부
};
 
void dfs(point cur) {
    for (int i = 0; i < 4; i++) {
        int nx = cur.x + dx[i];
        int ny = cur.y + dy[i];
        if(visited[nx][ny])
            continue;
        int nh = arr[nx][ny];
        int nlen = cur.len + 1;
        bool nchk = cur.chk;
        point nxt = {nx, ny, nh, nlen, nchk};
        bool flag = false; // dfs 실행할지 여부
        if (nxt.h < cur.h)
            flag = true;
        else {
            // 공사하지 않았고 공사 후 진행 가능한 경우
            if (!cur.chk && cur.h > nxt.h - K) {
                nxt.chk = true; // 공사 체크
                nxt.h = cur.h - 1; // 1만큼만 빼기
                flag = true;
            }
        }
        if (flag) {
            result = max(result, nxt.len);
            visited[nxt.x][nxt.y] = true;
            dfs(nxt);
            visited[nxt.x][nxt.y] = false;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen("../input.txt", "r", stdin);
 
    int tc;
    cin >> tc;
    for (int T = 1; T <= tc; T++) {
        highest = 0, result = 0;
        cin >> N >> K;
        arr = vector<vector<int> >(N + 2, vector<int>(N + 2, INT32_MAX));
        visited = vector<vector<bool> >(N + 2, vector<bool>(N + 2, false));
 
        // 값 저장
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> arr[i][j];
                highest = max(highest, arr[i][j]);
            }
        }
 
        // 탐색 시작
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (arr[i][j] < highest)
                    continue;
                point cur = {i, j, arr[i][j], 1, false};
                result = max(result, 1);
                visited[i][j] = true;
                dfs(cur);
                visited[i][j] = false;
            }
        }
        cout << "#" << T << " " << result << "\n";
    }
 
    return 0;
}