[맛있는물회] <SWEA알고리즘> 1949번 "등산로 조성"

문제 조건

---

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

등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.

등산로 부지는 아래 [Fig. 1]과 같이 숫자가 표시된 지도로 주어지며, 각 숫자는 지형의 높이를 나타낸다.

 

등산로를 만드는 규칙은 다음과 같다.

   ① 등산로는 가장 높은 봉우리에서 시작해야 한다.

   ② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
       즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

   ③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.

N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.

이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.


[예시]

위 [Fig. 1]과 같이 N = 5인 지도가 주어진 경우를 살펴보자.

가장 높은 봉우리는 높이가 9로 표시된 세 군데이다.

이 세 곳에서 출발하는 가장 긴 등산로 중 하나는 아래 [Fig. 2]와 같고, 이 때 길이는 5가 된다.
 

 

만약 최대 공사 가능 깊이 K = 1로 주어질 경우,

아래 [Fig. 3]과 같이 빨간색 부분의 높이를 9에서 8로 깎으면 길이가 6인 등산로를 만들 수 있다.
 

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

 

Input

---

1. 시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 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 크기의 지도 정보가 주어진다.

 

Output

---

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

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

 

생각한 아이디어

---

확실히 삼성 코테가 어렵긴하다.

먼저 K에 대한 이해가 필요하다. K번이 아니라 최대 K만큼 한번 봉우리를 깎을 수 있다.

 

미로 비슷한 문제여서 dfs인것은 접근을 했다. 

나는 먼저 전체 지도를 입력받고 가장 높은 봉우리를 뽑아서 List를 만들었다.

그리고 가장 높은 봉우리의 개수만큼 DFS를 진행한다.

재귀 DFS에서 가장 유의해야하는 점은 재귀가 끝나고 돌아왔을때 이전의 상태로 원상복구 시키는 작업이 필수적이다.

이 부분에서 상당히 곤란했다. 

 

여기서는 Visited (방문한 곳), Distance(움직인 거리), MAP(만약에 봉우리를 깎았다면 다시 원상복구 시켜줘야한다.) 이렇게 DFS 재귀에서 변경이 일어나는 부분을 재귀가 끝나고 바로 원상복구 시켜주어야 제대로 작동한다.

 

DFS는 2개의 케이스로 구분하였다.

먼저 다음에 움직일 좌표가 항상 0<= x, y < N 이어야만 한다.

 

1. 움직일 봉우리가 이전의 봉우리보다 낮다

-> 그렇다면 바로 움직여주면 된다.

 

2. 움직일 봉우리가 이전의 봉우리보다 높다. 그리고 아직 공사를 진행하지 않아서 봉우리를 깎을 수 있다.

-> 먼저 깎을 수 있는 최대치인 K값을 넣었을 때 움직일 봉우리가 이전 봉우리보다 작을 수 있냐 라고 물어봐야한다. 

 

그렇게 진행 후 다시 원상복구 작업을 시켜주고, DFS를 끝을 내면 된다.

역시 완전 탐색 문제는 많이 해야 노하우가 생길 것 같다.

 

소스코드

#1949 "등산로 조성"
#문자열에서는 find 되는데 정수 리스트에서는 find 안됨...그래서 인덱스 찾으려면 index를 써야한다.


def dfs(Distance, y,x,visited):
    global MaxDistance
    global K
    global flag
    
    for dir in range(0,4):
        new_y = y + dy[dir]
        new_x = x + dx[dir]
            #Insafe(y,x,, new_x) 
        if 0<=new_y MAP[new_y][new_x]: #이전의 봉우리보다 낮아야한다.
            #y,x 로 움직일 수 있다.
                visited.append((new_y,new_x))
                Distance += 1
                dfs(Distance, new_y,new_x,visited)

                if Distance >= MaxDistance:
                    MaxDistance = Distance

                ############되돌리는 부분
                Distance -= 1
                visited.pop()
        
            else :#만약 낮지않다면
                #MAP[x][y]를 MAP[old_x][old_y]보다 딱 한 칸 낮게 만들면 된다.
                
                depth = MAP[new_y][new_x] - MAP[y][x] + 1

                if flag == 1 and K >= depth and MAP[new_y][new_x] != 0:
                    #봉우리를 낮출 수 있다면
                    #낮출 수도 있고 k의 값이 충분하다.
                    flag = 0 
                    MAP[new_y][new_x] -= depth

                    visited.append((new_y,new_x))

                    Distance += 1
                    dfs(Distance, new_y,new_x,visited)

                    if Distance >= MaxDistance:
                        MaxDistance = Distance

                    ############되돌리는 부분
                    visited.pop()
                    Distance -=1
                    MAP[new_y][new_x] += depth #map 부분 다시 되돌리기
                    flag = 1

    
T = int(input())
for TC in range(1, T + 1):
    flag = 1 #지형 깎는 공사 진행했는지 안했는지
    N, K = map(int, input().split())
    MAP = list()
    top = 0 #최고 높이 봉우리 찾기
    topList = list()
    for i in range(N):#지도 입력
        arr = list(map(int,input().split()))
        MAP.append(arr)
        if top <= max(arr):
            top = max(arr)

    for y in range(0,N):
        for x in range(0,N):
            if MAP[y][x] == top:
                topList.append((y,x))

    dy = [-1,1,-0,0]
    dx = [0,0,-1,1]
    MaxDistance = -999
    
    j = len(topList)
    for i in range(j): #봉우리 개수만큼 출발점
        visited = list()
        Distance = 1
        start = topList.pop()
        start_y, start_x = start[0],start[1]
        visited.append((start_y, start_x))#시작점 추가

        dfs(Distance, start_y,start_x,visited)  
    print("#%d %d" %(TC,MaxDistance))

 

*파이썬 문법 정리