[ SW Expert Academy / 1949 ] 등산로 조성

투굠이 2020. 1. 8. 23:18

1. 문제 이해

입력값:
N (3 이상 8 이하)
K (1 이상 5 이하)
1 이상 20 이하 정수 (N 줄에 걸쳐)

유의해야 할 점:
1. 가장 높은 봉우리에서 시작 (첫 시작이 정해져 있음)
2. 높은 지역에서 낮은 지역으로 4방향 (같거나 대각선 불가)
3. 딱 한 곳을 정해서 최대 K만큼 지형 깎기 가능

N :정사각형 지도의 한 변의 길이
K : 최대 공사 가능 깊이

출력 값:
가장 긴 등산로의 길이

2. 문제 풀이 법

사용한 방법: DFS

1.가장 높은 봉우리의 높이를 구한다.
2. 가장 높은 봉우리(첫 시작이 됨)를 탐색하여 리스트(starts)로 저장한다.

starts의 각 start에 대해 DFS 함수를 실시한다.

인자 : x값, y값, 깎은 유무, 현재까지 등산로 길이

1. visited 체크 (왔던 길 다시 안 가려고)

2. 4방향 탐색

- 범위를 넘어간다면 리턴해준다
- visited가 체크되어있다면 넘어가 준다 ( 지나왔던 길 )
- 위에 해당되지 않은 지형의 높이를 구한다.

1) 그 높이가 현재 높이보다 작을 경우 dfs (그 지형 위치, 지형 높이, 깎은 유무, 현재 등산로 길이 + 1 )

2) elif 그 높이보다 크거나 같은데 깎은 적이 없는데 최대 깎은 길이가 현재 높이보다 작으면
dfs(그 지형 위치, 지형 높이 -1, 깎았다, 현재 등산로 길이 + 1)

- visited 다시 0으로 바꿔주기 (다음에 영향 미치니까!! 조합 같은 느낌)

2)에 지형 높이 -1 하는 것이 중요한 것 같다

3. 어려웠던 점

1. VISITED가 왜 필요한지 몰라서 한참 헤맸다.
2. DFS의 인자가 뭐가 필요한지 많이 필요해도 되는지 잘 몰라서 헤맸다.
--> 많아도 되나???? 평 씨가 알려줄 듯

def dfs(x, y, h, flag, t_ans):
    global ans
    visited[y][x] = 1
 
    if ans < t_ans: # 결과 값 넣어주기
        ans = t_ans
 
    for k in range(4): # 4방향 탐색
        temp_x = x + dx[k]
        temp_y = y + dy[k]
 
        if temp_x < 0 or temp_x >= N or temp_y < 0 or temp_y >= N : # 범위체크
            continue
            
        if visited[temp_y][temp_x] == 1: # 방문체크
            continue
 
        temp_h = mountain[temp_y][temp_x]

        if h > temp_h:
            dfs(temp_x,temp_y, temp_h, flag, t_ans+1)
            visited[temp_y][temp_x] = 0 
        elif flag != 0:
            if mountain[temp_y][temp_x] - K < h:
                dfs(temp_x, temp_y, h-1, 0, t_ans+1)
                visited[temp_y][temp_x] = 0
 
T = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
 
for tc in range(1,T+1):
    N, K = map(int,input().split())
    mountain = [list(map(int,input().split()))for _ in range(N)]
    ans = 0
    starts = [] # [[x,y]
 
    m_s = max(sum(mountain,[])) #최댓값
    for i in range(N):
        for j in range(N):
            if mountain[i][j] == m_s:
                starts.append([j,i])
 
    for start in starts:
        mx,my = start
        visited = [[0 for _ in range(N)] for _ in range(N)]
        dfs(mx, my, m_s, 1, 1)
 
    print('#{} {}'.format(tc,ans))

4. 배운 점

VISITED 체크하고 다시 0으로 되돌리는 위치