SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
'벽 부수고 이동하기'와 유사하다. 한 번만 팔 수 있으니까? bool을 써야겠다.
팠을 때 digged를 true로 만들고 digged가 true이면 이제 더 이상 건들일 수 없다.
'빙산' 문제를 떠올리면, 등산로 조성을 할 때 주어진 배열은 건들이면 안된다는 것을 배웠다.
이 문제도 마찬가지이다. 최대 높이가 여러 개 있으므로 배열은 건들이면 안된다.
이 문제는 최단거리의 문제가 아니다. 등산로의 최대 길이를 구하는 문제이다.
DFS를 써야함을 알 수 있다.
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
int num, dig, result;
int arr[8][8];
bool check[8][8];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int dfs(int x, int y, int height, bool digged)
{
check[x][y] = true;
int cnt = 0;
for (int k = 0; k < 4; k++)
{
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && ny >= 0 && nx < num && ny < num && !check[nx][ny])
{
if (arr[nx][ny] < height)
{
cnt = max(cnt, dfs(nx, ny, arr[nx][ny], digged));
}
else
{
//digged가 false이고 팠을 때 등산로 조성이 된다
if (!digged && arr[nx][ny] - dig < height)
{
cnt = max(cnt, dfs(nx, ny, height - 1, true));
}
}
}
}
// 재귀가 끝날 때 방문했던 정점들을 다 false로 바꿔줘야한다!
check[x][y] = false;
// 재귀가 돌아오면서 cnt가 늘어간다.
return cnt + 1;
}
int main()
{
int test, maxi;
cin >> test;
for (int t = 1; t <= test; t++)
{
cin >> num >> dig;
result = 0;
maxi = 0;
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
cin >> arr[i][j];
check[i][j] = false;
maxi = max(maxi, arr[i][j]);
}
}
for (int i = 0; i < num; i++)
{
for (int j = 0; j < num; j++)
{
if (arr[i][j] == maxi)
{
// digged는 false로 들어간다
int tmp = dfs(i, j, arr[i][j], false);
result = max(result, tmp);
}
}
}
cout << "#" << t << " " << result << '\n';
}
return 0;
}
|
cs |
cnt = max(cnt, dfs(nx, ny, height - 1, true));
이 부분이 가장 중요!
파야 하는 경우는 같거나 클 경우이다. 등산로는 내림차순에 최대가 되야하므로
깊게 파야할 이유가 없다!
그러므로 height - 1을 넣는다.
