[C++] SWEA 1949 - 등산로 조정

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

SW Expert Academy

<풀이>

1. 가장 높은 봉우리에서 시작해서 등산로를 찾습니다.

2. 만들 수 있는 등산로 중 가장 긴 등산로를 찾고 그 길이를 출력한다.

 

<해법>

1. 문제를 해결한 핵심 알고리즘

=> 지형을 깎는다는 조건이 없다면, 제일 높은 봉우리에서 사방을 찾아가며 내려가는 문제입니다. 저는 문제를 읽고 DFS가 떠올랐습니다. 

 

2. 봉우리를 깎는 방법

=> 봉우리는 1~K만큼 깎을 수 있습니다. 하지만, 1~K만큼 모두 깎아볼 필요는 없습니다. 가장 길게 만들 수 있는 등산로를 찾는 문제이기 때문에, 현재 높이보다 1만큼만 낮게 깎아야 가장 긴 등산로를 찾을 수 있습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, K;
int map[8][8];
bool visited[8][8];
int answer;
 
bool isInner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    return true;
}
 
int findRoute(int x, int y, bool cut) {
 
    int ret = 1;
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (!isInner(nx, ny) || visited[nx][ny]) continue;
 
        if (map[nx][ny] < map[x][y]) {
            visited[nx][ny] = true;
            ret = max(ret, findRoute(nx, ny, cut) + 1);
            visited[nx][ny] = false;
        }
        else {
            if (!cut && map[nx][ny] - K < map[x][y]) {
                int tmp = map[nx][ny];
                map[nx][ny] = map[x][y] - 1; //현재 지형보다 1만큼만 낮게 깎음
                visited[nx][ny] = true;
                ret = max(ret, findRoute(nx, ny, 1) + 1);
                map[nx][ny] = tmp;
                visited[nx][ny] = false;
            }
        }
    }
 
    return ret;
}
 
void solution() {
    //1. 가장 높은 봉우리 찾기
    int peek = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] > peek) {
                peek = map[i][j];
            }
        }
    }
 
    //2. 가장 높은 봉우리에서 등산로 찾기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] == peek) {
                visited[i][j] = true;
                answer = max(answer, findRoute(i, j, false));
                visited[i][j] = false;
            }
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, K = 0;
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> N >> K;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

DFS와 구현에 대해 알아볼 수 있는 문제였습니다.