1. 문제 소개

등산로를 조성하려고 한다.

등산로를 만들기 위한 부지는 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부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다

2. 풀이 방법

1. 이차원 배열로 등산로를 생성하고 가장 높은 봉우리 값을 구한다.
2. 가장 높은 봉우리 값의 좌표이면 dfs를 시작
3. dfs 함수 안에서 델타범위 이용하여 상하좌우 재귀로 탐색

3. 코드

def dfs(y,x):
    global cnt, visited, ans, ch

    cnt += 1
    ans = max(cnt, ans)

    for i in range(4):
        ny = y+dr[i]
        nx = x+dc[i]
        if 0<=ny<N and 0<=nx<N and visited[ny][nx] ==0:     # 인덱스 범위 설정 및 방문한적없을때
            if trail[ny][nx] < trail[y][x]: # 새로운 길이 기존의 길보다 낮을때
                visited[ny][nx] = 1 # 방문체크
                dfs(ny,nx)  # dfs
                visited[ny][nx] =0  # 방문 초기화
                cnt -=1# cnt -1
            elif ch ==0 and trail[ny][nx] >= trail[y][x]: # 만약 한번도 안깎았을대, 새로운 트레일 높이 -k가 기존 트레일보다 낮을때
                ch=1
                for i in range(1,K+1):  # 어떤게 최적의 값인지 모르므로 전부 다 탐색
                    trail[ny][nx] -= i  # 새로운 트레일 값 변경
                    if trail[ny][nx] < trail[y][x]: # i를 빼준값이 기존의 트레일 높이 보다 낮을때
                        visited[ny][nx] = 1 # 방문 체크
                        dfs(ny,nx)  # dfs
                        visited[ny][nx] = 0 # 방문 초기화
                        cnt -=1 # 카운트 초기화
                    trail[ny][nx] = trail[ny][nx] + i   # 다시 값 초기화
                ch =0
dr = [-1,1,0,0]
dc = [0,0,-1,1]


T = int(input())
for t in range(1,T+1):
    N, K = map(int, input().split())
    trail = [list(map(int, input().split())) for _ in range(N)]
    max_num = 0
    ans = 0
    for i in range(N):
        temp = max(trail[i])
        if max_num < temp:
            max_num = temp
    for y in range(N):
        for x in range(N):
            if trail[y][x] == max_num:
                cnt = 0
                ch = 0
                visited = [[0] * N for _ in range(N)]
                visited[y][x] =1
                dfs(y,x)


    print(f'#{t} {ans}')

마치며

문제를 푼 이후에 다른 사람들 코드를 보니 함수에 매개변수를 추가하여 좀더 코드를 간결하게 구현한것을 보았다. 사실 매개변수를 3개 이상 사용해본적이 없어 위의 같은 방법으로 문제들을 자주 풀어왔는데, 매개변수를 좀 더 활용해보는 연습을 해야겠다는 생각이 들었다.