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이 된다.
[제약 사항]
-
시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
-
지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
-
최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
-
지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.
-
지도에서 가장 높은 봉우리는 최대 5개이다.
-
지형은 정수 단위로만 깎을 수 있다.
-
필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.
[입력]
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.
그 다음 N개의 줄에는 N * N 크기의 지도 정보가 주어진다.
[출력]
테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다
2. 풀이 방법
- 이차원 배열로 등산로를 생성하고 가장 높은 봉우리 값을 구한다.
- 가장 높은 봉우리 값의 좌표이면 dfs를 시작
- 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개 이상 사용해본적이 없어 위의 같은 방법으로 문제들을 자주 풀어왔는데, 매개변수를 좀 더 활용해보는 연습을 해야겠다는 생각이 들었다.
* 문제 출처: https://swexpertacademy.com/
