요약
- visited 에 길만 표시한다.
- 리턴되고 나면 visited 는 지워준다. ( 다른 경로로 그 점을 통과해야 할 수도 있으니까)
- 깎은 높이는 visited 에만 표시한다.
- 리턴되기 전에 깎은 횟수가 1이라면, map과 visited를 비교해서 다를 경우 cutting을 0으로 만들어준다.
문제
① 등산로는 가장 높은 봉우리에서 시작해야 한다.
② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.
③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.
[제약 사항]
1. 시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.
5. 지도에서 가장 높은 봉우리는 최대 5개이다.
6. 지형은 정수 단위로만 깎을 수 있다.
7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.
[입력]
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.
[출력]
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.
풀이
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
struct Node {
int row, col;
};
int map[8][8] = { 0, };
int visited[8][8] = { 0, };
int N, K;
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
int flag;
int cutting = 0;
int maxflag;
void calc(int row, int col) {
// 상하좌우 갈 수 있는 경로 확인
// 현재위치보다 작으면 갈 수 있다.
// 깎은 횟수를 표시해뒀다가 한 번도 안깎았으면 한 번 깎을 수 있음
// 단, K만큼만 깎을 수 있음
// 단 그 점에서 되돌아 나오게되면 지도 원상복구
// 깎는건 나보다 하나 작게만 깎아주면 된다
for (int i = 0; i < 4; i++) {
int nr = row + dr[i];
int nc = col + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
if (visited[nr][nc]) continue;
if (map[nr][nc] - K >= visited[row][col]) continue;
if (map[nr][nc] >= visited[row][col] && cutting == 1) continue;
if (map[nr][nc] >= visited[row][col]) {
visited[nr][nc] = visited[row][col] - 1;
cutting++;
}
else visited[nr][nc] = map[nr][nc];
flag++;
calc(nr, nc);
if (flag > maxflag) maxflag = flag;
flag--;
}
if (cutting) {
if (map[row][col] != visited[row][col])cutting--;
}
visited[row][col] = 0;
// 포문을 그냥 통과했다 == 상하좌우 어디로도 가지 못했다
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N >> K;
int maxheight = -1;
vector <Node> v;
memset(map, 0, sizeof(map));
// 1. 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] > maxheight) maxheight = map[i][j];
}
}
// 2. 출발 가능 지점(최대 높이) 기록
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == maxheight) v.push_back({ i,j });
}
}
// 3. 기록된 최대 높이 마다의 최대 등산로 길이 계산
int maxdist = 0;
for (int i = 0; i < v.size(); i++) {
memset(visited, 0, sizeof(visited));
visited[v[i].row][v[i].col] = map[v[i].row][v[i].col];
flag = 1;
maxflag = 1;
calc(v[i].row, v[i].col);
if (maxflag > maxdist) maxdist = maxflag;
}
v.clear();
cout << "#" << tc << " " << maxdist << "\n";
}
return 0;
}