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

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

SW Expert Academy

이 문제는 갈 수 있는 최대 길이를 구하는 문제이므로 dfs를 이용해서 풀 수 있다.

dfs의 depth가 문제의 최대 길이가 된다.

 

풀이

1. 입력받은 지형의 높이 중 가장 높은 높이를 저장해 놓는다.

 

2. 해당 높이를 가지고 있는 지형(가장 높은 봉우리)의 좌표를 벡터에 저장한다.

 

3. 가장 높은 봉우리로부터 출발할 수 있으므로 위에서 저장한 좌표에서 각각 출발해본다.

 

4. 출발할 때는, 모든 칸을 0번부터 k번까지 깎아보는 모든 경우에서 출발(dfs탐색)한다. 해당 칸을 깎은 경우에서 돌아온다면 깎은 만큼 다시 더해준다. (1칸만 깎을 수 있으므로)

 

5.dfs탐색을 할 때는 문제 조건에 따라 이동할 칸이 현재 지형보다 더 낮아야 이동할 수 있고, 다음 칸으로 이동할 때마다 길이를 하나씩 늘려준다.

 

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int n, k, ans;
int map[8][8];
bool visit[8][8];
vector<pair<int, int>> toplist;
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
 
void dfs(int x, int y, int len) {
    //방문 체크
    visit[x][y] = true;
    //최대 길이를 저장
    if (ans < len) ans = len;
 
    //가로방향, 세로방향으로 이동
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        //범위 체크
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        //방문 체크
        if (visit[nx][ny]) continue;
        //같거나 높은지형으로는 갈 수 없다.
        if (map[nx][ny] >= map[x][y]) continue;
 
        //길이를 하나 늘린채로 (nx, ny)로 이동
        dfs(nx, ny, len+1);
 
        //탐색에서 돌아온 후에 방문체크를 지워준다.
        visit[nx][ny] = false;
    }
 
 
}
 
void solve() {
 
    int vsize = toplist.size();
    int x, y;
 
    //모든 가장 높은 봉우리
    for (int t = 0; t < vsize; t++) {
        x = toplist[t].first;
        y = toplist[t].second;
 
        //모든 칸을 0부터 k만큼 깎아본다.
        for (int l = 0; l <= k; l++) {
 
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    //현재 시작하는 봉우리인 경우 깎지 않는다.
                    if (i == x && y == j) continue;
 
                    //(i,j)칸을 l만큼 깎는다.
                    map[i][j] -= l;
                    //visit 배열 초기화 후에
                    memset(visit, false, sizeof(visit));
                    //dfs탐색
                    dfs(x,y, 1);
 
                    //탐색에서 돌아온 후 다시 l을 더해준다.
                    map[i][j] += l;
                }
            }
 
        }
 
 
    }
 
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> n >> k;
 
        int maxh = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
                //봉우리의 최댓값을 저장
                if (maxh < map[i][j]) maxh = map[i][j];
            }
        }
 
        //새로운 테스트케이스를 위해서 초기화
        toplist.clear();
        ans = 0;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //가장 높은 봉우리들을 벡터에 넣는다.
                if (map[i][j] == maxh) toplist.push_back(make_pair(i, j));
            }
        }
 
        solve();
        
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
    return 0;
}