문제 URL : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
문제 접근법:
어렵지 않은 문제입니다. 문제에 나와있는 조건대로만 만들어주면 됩니다.
접근1 : 등산로가 가장 높은 봉우리에서 시작한다 -> 가장높은 것을 늘 새롭게 좌표를 갱신 같은것일경우 추가만하면 됩니다.
접근 2: 높은곳에서 낮은곳으로 좌우상하 네방향으로 이동만합니다.(dfs를 이용했습니다.)
접근 3: 최대 깊이 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
|
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int map[10][10];
vector<pair<int, int>> v;
int visit[10][10];
int res;
bool isrange(int y, int x)
{
if (0 <= y&&y < n && 0 <= x&&x < n)
return true;
return false;
}
void dfs(int y, int x,int height, int k, int cnt = 1)
{
res = max(res, cnt);
visit[y][x] = 1;
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && visit[ny][nx] == 0){
if (height>map[ny][nx])//높은곳에서 낮은곳으로 이동
dfs(ny, nx, map[ny][nx],k,cnt + 1);
else if (height+k>map[ny][nx])//그다음이 현재보다 높다면 최대 k만큼깎아서 이동할수있는지
{
int t = 1;
while (map[ny][nx] - t >= height)//k만큼 깎는게아니라 최소한으로 깎아 그높이를 최대로 만들어야 다음 이동할때 최대한으로 이동할수있게 만들수있음 핵심입니다.
t++;
dfs(ny, nx, map[ny][nx] - t, 0, cnt + 1);//깍고 지나갔다면 더이상 깎을수없도록 k를 0으로만들면 됩니다.
}
}
}
visit[y][x] = 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int te;
cin >> te;
for (int test = 1; test <= te; test++)
{
int k;
cin >> n >> k;
int 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]){//접근1 가장높은곳을 새롭게 갱신
v.clear();
v.push_back({ i, j });
Max = map[i][j];
}
else if (Max == map[i][j])//Max와 같다면 좌표를 추가하면됨
v.push_back({ i, j });
}
}
res = 0;
for (auto it : v){
dfs(it.first, it.second,map[it.first][it.second], k);
}
cout << "#" << test << " " << res << "\n";
}
}
|
cs |
궁금한점 혹은 모르는점 혹은 잠재적인 오류가 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'SWEA' 카테고리의 다른 글
| [SWEA] 1953 탈주범 검거(모의 SW 역량테스트) (0) | 2020.10.02 |
|---|---|
| [SWEA] 5650 핀볼 게임(모의 SW 역량테스트) (0) | 2020.09.30 |
| [SWEA] 5653 줄기세포배양(모의 SW 역량테스트) (0) | 2020.09.28 |
| [SWEA] 4013 특이한 자석 (모의 SW 역량테스트) (0) | 2020.09.27 |
| [SWEA] 9940 순열1 (0) | 2020.09.15 |
