SWEA 1949. 등산로 조성 (C++)

모옹·2023년 2월 18일
0

알고리즘

목록 보기
2/18

요약

  1. visited 에 길만 표시한다.
  2. 리턴되고 나면 visited 는 지워준다. ( 다른 경로로 그 점을 통과해야 할 수도 있으니까)
  3. 깎은 높이는 visited 에만 표시한다.
  4. 리턴되기 전에 깎은 횟수가 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;
}

0개의 댓글