Posts 알고리즘 - 1949. [모의 SW 역량테스트] 등산로 조성
Post
Cancel

알고리즘 - 1949. [모의 SW 역량테스트] 등산로 조성

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로 상-하-좌-우 진행을 하는 전체 과정 및 깎는 여부를 추가하는 과정은 다음과 같습니다.

    1. 다음으로 갈 곳의 높이가 현재 내 위치보다 낮다면 이동한다.

    2. 그렇지 않다면,

      2-1. 다음으로 갈 곳의 높이에 최대 K를 뺀 값이, 현재 내 위치의 높이보다 작다면, 다음의 그 위치를 최대 K의 값으로 뺀 다음 dfs를 진행한다.

    3. dfs를 등산로를 만들 수 없을 때까지 계속 진행한다.

    4. 만들 수 없을 때까지 도달했을 경우, 해당 길이를 저장해 두고, 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;
	}

}

[GitHub] GitHub Action을 사용하여 자동 스크래핑(scraping)과 Push 구현하기

[백준] 9465번 - 스티커