SW Expert Academy 의 1949번 - 등산로 조성 문제입니다.
문제 조건
N * N 으로 이루어진 등산로 부지가 존재합니다.
이 문제는 최대한 긴 등산로를 구해야 합니다.
N * N의 타일에서 가장 숫자가 높은 곳이, 가장 높은 봉우리입니다.
이 봉우리에서, 숫자가 작아지는 방향으로 가는 길이 등산로가 될 수 있습니다.
위와 같은 상황은, 가능한 등산로들의 몇몇 예시가 될 수 있습니다.
등산로 형성에는 몇 가지 규칙이 존재합니다.
- 등산로는 가장 높은 봉우리에서 시작해야 한다.
- 높은 지형에서 낮은 지형으로 가로 혹은 세로 방향으로만 연결 가능하다.
- 대각선 방향으로는 불가하다.
- 긴 등산로를 만들기 위해 단 한 곳만을 정해, 최대 K 깊이만큼 높이를 깎는 시행을 할 수 있다.
마지막 규칙에 의해, 만약 K=1 이었을 경우, 기존의 9가 있던 자리를 1만큼 깎는다면, 위처럼 N * N 부지에서 가장 긴 등산로(길이 6)를 구할 수 있게 됩니다.
Input
한 개의 테스트 케이스 당
- 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.
Output
테스크 케이스 당, 가장 긴 등산로의 길이를 출력한다.
생각한 아이디어
이전에 살펴본 단지번호 매기기 문제와 같이, 각 타일별 방문을 dfs로 진행합니다.
가장 봉우리가 높은 곳에서 시작합니다. 타일 한 칸당, 상/하/좌/우를 보면서 갈 수 있는 곳으로 이동합니다.
이 문제에서 다른 칸으로 갈 수 있는 조건은 ‘상→하→좌→우 중 나보다 더 높이가 작은 칸’ 으로의 이동입니다.
상→하→좌→우 중 아래(하)로 이동할 때의 상황을 살펴보겠습니다.
- 9->6으로 이동 후, 6도 상→하→… 를 살펴봅니다. 6에서 위로는(상) 갈 수 없으므로, 3으로 내려옵니다.
- 3에서도 위로는(상) 갈 수 없으므로, 2로 내려옵니다(하).
- 2에서는 위로도 갈 수 없으며, 아래의 7은 2보다 크므로 갈 수 없습니다. 그 다음 2 기준으로 →좌→우로 dfs를 진행하지만 이 또한 갈 수 없습니다. (2의 오른편인 3도 더 크므로 갈 수 없음)
따라서 9-6-3-2 경로에서는 더 이상 추가 전진할 수 없으므로, 2에서 back 하여 다시 3으로 갑니다.
3도 마찬가지로 →좌→우 를 마저 확인합니다. 오른쪽도 4이므로 3에서 갈 수 없습니다.
이렇게 dfs를 진행하여, 처음 시작 위치인 9에 올 때 까지 등산로 형성 과정을 반복합니다.
그렇다면, 최대 K 만큼 깎을 수 있는 상황은 어떨까요?
가장 높은 봉우리 중 하나인 (2,4) 위치의 9에서 새로 dfs를 시작합니다.
- 상/하 방향은 먼저 보았다고 가정하고, 이제 왼쪽으로 갈 차례입니다.
- 9의 왼쪽도 9가 있는데, 원래 상태로는 이쪽으로 가지 못합니다.
- 하지만 문제 조건에 의해 등산로 중 단 한곳을 최대 K만큼 깎을 수 있습니다.
- 그러므로 9의 왼쪽에 있던 9를 K=1만큼 깎는다면 8이 되고, 따라서 위 그림처럼 시작 위치인 9에서 왼쪽으로 이동 가능해집니다.
그리고 dfs를 계속 진행하여, 9-8-7-3-2-1 의 등산로 형성이 가능해집니다.
즉, dfs로 상-하-좌-우 진행을 하는 전체 과정 및 깎는 여부를 추가하는 과정은 다음과 같습니다.
다음으로 갈 곳의 높이가 현재 내 위치보다 낮다면 이동한다.
그렇지 않다면,
2-1. 다음으로 갈 곳의 높이에 최대 K를 뺀 값이, 현재 내 위치의 높이보다 작다면, 다음의 그 위치를 최대 K의 값으로 뺀 다음 dfs를 진행한다.
dfs를 등산로를 만들 수 없을 때까지 계속 진행한다.
만들 수 없을 때까지 도달했을 경우, 해당 길이를 저장해 두고, Max 값 여부를 파악한 뒤, 해당 경로의 visit 배열을 모두 초기화한다.
4-1. 2-1에서 K만큼 뺀 후 진행했다면, dfs 끝에 도달했을 때는 4의 과정을 진행하고 추가적으로 K만큼 뺀 곳에 다시 K를 더하여 복구하여 준다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
//상,하,좌,우
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int visit[9][9];
int arr[9][9];
int cnt;
int maxCnt = -1;
int K;
int cutINF;
void findPath(int y, int x, int N) {
visit[y][x] = 1;
for (int i = 0; i < 4; i++) {
int ty = dy[i] + y;
int tx = dx[i] + x;
// 상,하,좌,우 중 갈 수 있는 case
if (ty >= 0 && ty < N && tx >= 0 && tx < N) {
// 다음 갈 곳에 방문하지 않았고, 나보다 높이가 작아 이동 가능하다면
if (visit[ty][tx] == 0 && arr[y][x] > arr[ty][tx])
{
visit[ty][tx] = 1; cnt += 1;
findPath(ty, tx, N);
if (maxCnt <= cnt)
maxCnt = cnt;
cnt -= 1;
visit[ty][tx] = 0;
}
// 나보다 높이가 크거나 같아 이동 불가했다면
else if(arr[y][x] <= arr[ty][tx]) {
for (int mk = 1; mk <= K; mk++) {
// 다음 갈 곳이 방문하지 않았고, 최대 K만큼 깎은 값이 나보다 작다면 이동
// 단, 한 경로를 만들어갈 때 단 한번만 깎을 수 있으므로,
// cutINF 전역변수로 단 한번 깎았는지 여부를 저장
if (visit[ty][tx] == 0 && arr[y][x] > (arr[ty][tx]) - mk && cutINF == 0) {
cutINF = 1; visit[ty][tx] = 1; cnt += 1;
arr[ty][tx] = arr[ty][tx] - mk;
findPath(ty, tx, N);
if (maxCnt <= cnt)
maxCnt = cnt;
cnt -= 1; cutINF = 0;
arr[ty][tx] = arr[ty][tx] + mk;
visit[ty][tx] = 0;
}
}//end inner for
}//end inner else
}//end outer if
} //end outer for
}//end function
int main() {
int T;
int N, input;
int maxPath = -1;
int maxValue = -1;
vector <pair<int, int>> maxElements;
scanf("%d", &T);
for (int t = 0; t < T; t++) {
scanf("%d %d", &N, &K);
// N * N input 입력받기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &input);
arr[i][j] = input;
if (input >= maxValue)
maxValue = input;
}
}
// maxValue를 가지는 위치 저장
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (arr[i][j] == maxValue)
maxElements.push_back({ i,j });
}
}
// dfs 시작 (최대 봉우리 위치들에서만 시작)
for (int i = 0; i < maxElements.size(); i++) {
findPath(maxElements[i].first, maxElements[i].second, N);
for (int j = 0; j < 9; j++) {
for (int k = 0; k < 9; k++) {
visit[j][k] = 0;
}
}
cnt = 0;
}
printf("#%d %d\n", t+1, maxCnt+1);
maxCnt = -1;
maxElements.clear();
maxValue = -1;
}
}