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

문제

SWEA 모의 SW 역량테스트 - 1949 등산로 조성

SW Expert Academy

---

문제 풀이

접근 방식

가장 높은 봉우리에서 시작하여 가장 긴 등산로를 조성하는 문제이다.

등산로를 조성하기 위해서는 상하좌우 네 방향을 탐색하여 이전의 높이보다 낮은 곳으로만 연결해야하고,

딱 한번 산의 높이를 깎는 공사를 할 수 있다.

 

우선, 입력을 받으며 가장 높은 봉우리의 위치를 찾아 highest에 넣어주었다.

그 다음, 그 위치들에서부터 DFS 탐색을 시작하여 가장 긴 등산로를 찾아주었다.

DFS 탐색을 위해 DFS 함수를 만들어주었고, visit 벡터를 활용하여 모든 경우를 탐색해주었다.

DFS 함수는 위치(x, y)와 등산로의 길이(cnt), 공사 여부(check)를 매개변수로 갖도록 하였다.

 

공사를 하지 않아도 갈 수 있는 경우에는

매개변수에 위치(nx, ny)와 cnt+1, check를 넣어 DFS 함수를 재귀적으로 수행하도록 하였다.

공사를 해야만 갈 수 있고 공사를 아직 안한 상태인 경우(check가 false인 경우)에는

map[nx][ny]의 값을 (현재 높이 - 1)로 설정해주고,

DFS(nx, ny, cnt+1, !check) 실행 후 map[nx][ny]의 값을 다시 원래대로 돌려놓아주었다.

(처음에는 map[nx][ny]의 값을 now - K의 값으로 설정했었는데, 그렇게 하면 now-1로 설정했을 때보다 갈 수 있는 곳이 적어져서 최선이 아니기 때문에 모든 테스트 케이스를 통과할 수 없다.)

최종적으로 이동을 마치면 answer과 cnt값을 비교하여, answer에 최댓값이 저장될 수 있도록 하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
using namespace std;
 
vector<vector<int>> map;
vector<vector<int>> visit;
int N, K, answer;
int dirs[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
void DFS(int x, int y, int cnt, bool check) {
    int nx, ny;
    int now = map[x][y];
    for (int i = 0; i < 4; i++) {
        nx = x + dirs[i][0];
        ny = y + dirs[i][1];
 
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (visit[nx][ny]) continue;
 
        if (now > map[nx][ny]) {
            visit[nx][ny] = 1;
            DFS(nx, ny, cnt + 1, check);
            visit[nx][ny] = 0;
        }
        else if (!check && now > map[nx][ny] - K) {
            visit[nx][ny] = 1;
            int temp = map[nx][ny];
            map[nx][ny] = now - 1;
            DFS(nx, ny, cnt + 1, !check);
            map[nx][ny] = temp;
            visit[nx][ny] = 0;
        }
        else {
            if (answer < cnt)
                answer = cnt;
        }
    }
}
 
int main(int argc, char** argv) {
    int test_case;
    int T, MAX;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기 & 가장 높은 봉우리 찾기
        cin >> N >> K;
        map.assign(N, vector<int>(N));
        visit.assign(N, vector<int>(N));
        vector<pair<int, int>> highest;
        MAX = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
                if (MAX < map[i][j]) {
                    MAX = map[i][j];
                    highest.clear();
                    highest.push_back({ i,j });
                }
                else if (MAX == map[i][j]){
                    highest.push_back({ i,j });
                }
            }
        }
 
        // 가장 긴 등산로 찾기
        answer = 1;
        for (auto i : highest) {
            bool check = false;
            visit[i.first][i.second] = 1;
            DFS(i.first, i.second, 1, check);
            visit[i.first][i.second] = 0;
        }
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}

실행 결과