[SWEA] 1949_등산로 조성 (DFS 이용)

📕 문제

등산로를 조성하려고 한다.
등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.
등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.
 

 

등산로를 만드는 규칙은 다음과 같다.
   ① 등산로는 가장 높은 봉우리에서 시작해야 한다.
   ② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
       즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.
   ③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.

[예시]
위 [Fig. 1]과 같이 N = 5인 지도가 주어진 경우를 살펴보자.
가장 높은 봉우리는 높이가 9로 표시된 세 군데이다.
이 세 곳에서 출발하는 가장 긴 등산로 중 하나는 아래 [Fig. 2]와 같고, 이 때 길이는 5가 된다.
 

 

만약 최대 공사 가능 깊이 K = 1로 주어질 경우,
아래 [Fig. 3]과 같이 빨간색 부분의 높이를 9에서 8로 깎으면 길이가 6인 등산로를 만들 수 있다.
 

이 예에서 만들 수 있는 가장 긴 등산로는 위와 같으며, 출력할 정답은 6이 된다.

[제약 사항]
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보다 작게 만드는 것도 가능하다.

 

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.

 

[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.

 

💡 풀이법

1. 최대한 깊이 가야하는 문제이기 때문에 dfs를 이용했다.

2. 가장 높은 곳부터 시작해야 한다고 했기 때문에 맵을 다 돌면서가장 높은 높이를 먼저 구한다.

3. 다시 맵을 다 돌면서 가장 높은 높이를 만나면 dfs를 실행한다.

4. dfs의 인수는 좌표, 지금까지의 거리, 공사를 했는지 유무가 담긴다.

5. 일반적인 dfs와는 다르게 한번 산을 최대 k만큼 깎을 수 있는 기회가 있기 때문에 다음에 갈 지대가 지금보다 높을 때랑 낮을 때로 경우를 나누어 준다.

6. dfs가 실행되면 먼저 현재 좌표를 방문 체크 해준다.

7. 다음에 갈 지대가 지금보다 낮다면 바로 갈 수 있기 때문에 거리를 1 키워주고 다음 좌표로 dfs를 다시 실행시킨다.

8. 다음에 갈 지대가 지금보다 같거나 높고, 공사를 아직 하지 않았고, 산을 깎아야하는 정도가 k보다 크지 않다면 다음 가야할 지대를 현재 지대보다 1 작게 깎아주고 역시 다음 좌표로 dfs를 실행시킨다.

(단, dfs가 끝나면 다시 깎은 지대를 원상복구 시켜줘야 함)

9. dfs 마지막에 다시 방문 체크를 풀어줘야 다음 경로에서 또 그 위치를 갈 수 있게 된다.

10. dfs를 돌면서 지금까지의 거리가 ans보다 크면 ans를 지금까리의 거리로 바꿔준다.

(ans는 가장 긴 등산로의 길이를 담을 변수이다)

 

dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dfs(x, y, dist, K):
    global ans

    if dist > ans:
        ans = dist

    visited[x][y] = 1

    for dx, dy in dxy:
        nx, ny = x + dx, y + dy

        if -1 < nx < N and -1 < ny < N and visited[nx][ny] == 0:
            if mountain[nx][ny] < mountain[x][y]:
                dfs(nx, ny, dist+1, K)
            elif K and K > mountain[nx][ny] - mountain[x][y]:
                tmp = mountain[nx][ny]
                mountain[nx][ny] = mountain[x][y] - 1
                dfs(nx, ny, dist+1, 0)
                mountain[nx][ny] = tmp

    visited[x][y] = 0

T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    mountain = [list(map(int, input().split())) for _ in range(N)]

    top = 0
    for i in range(N):
        for j in range(N):
            if mountain[i][j] > top:
                top = mountain[i][j]

    ans = 0
    visited = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if mountain[i][j] == top:
                dfs(i, j, 1, K)

    print('#{} {}'.format(tc, ans))