[모의 SW 역량테스트] 1949 등산로 조성 (Python)

문제 출처

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

문제

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

등산로를 만들기 위한 부지는 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. 시간 제한 : 최대 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 크기의 지도 정보가 주어진다.

[출력]

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

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

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

 

10        // 총 테스트 케이스 개수 T = 10 5 1       // 첫 번째 테스트 케이스, N = 5, K = 1, 본문 예제 9 3 2 3 2  // 지도 정보 6 3 1 7 5 3 4 8 9 9 2 3 7 7 7 7 6 5 5 8 3 2       / 두 번째 테스트 케이스, N = 3, K = 2 1 2 1     // 지도 정보 2 1 2 1 2 1 …        // 나머지는 sample_input.txt 참조

#1 6 #2 3 #3 7 #4 4 #5 2 #6 12 #7 6 #8 7 #9 10 #10 19

 

풀이

DFS를 활용해 완전 탐색하였다. 배열 모든 부분을 DFS로 시작해 탐색할 필요가 없이 최대 봉우리 지점만 탐색하면 되었고 그 봉우리마저 최대 5개 밖에 되지 않아 충분히 완전탐색이 가능하다고 생각했다.

먼저 각 봉우리의 최대높이를 구한 뒤, 배열을 for문을 돌려 봉우리를 찾고 DFS를 시작하였다.

기본적으로 4방향을 체크하며 4방향 체크를 다하고도 갈 곳이 없다면 현재 저장된 max 길이와 비교 후 return 하였다.

굴삭을 어떻게 할 것인지에 대해서는 단 한 번만 굴삭을 허용하기에 굴삭을 했는지에 대한 check parameter를 만들어 0이면 아직 안했고 1이면 굴삭을 했다는 식으로 만들었다.

굴삭조건의 경우에는 현재 지점에서 다음 지점이 작다면 등산로로 활용 할 수 있기에 굴삭을 할지 말지를 아얘 고려하지 않았고 다음지점이 같거나 크다면 굴삭을 해야 등산로로 활용할 수 있기에 check paramter가 0이라면 굴삭을 얼마나 할지 판단하였다.

주의할 점은 첫 시작 봉우리를 방문 배열에 체크해줘야하는 것이다. DFS를 탐색하며 방문배열을 통해 한번 방문했던 곳에 다시 가서 등산로 길이(cnt)를 늘리지 않도록 방지하였는데 정작 시작지점을 넣지 않아 몇몇 테스트 케이스에서 정답이 나오지 않는 시행착오를 겪었다.

 

코드

def dfs(row,col,k,check,cnt): # 행,열, 굴삭깊이, 굴삭했는지 체크 parameter, 등산로길이 
    global max_cnt
    for i in range(4): # 4방향 체크
        if 0 <= row + dx[i] < N and 0 <= col + dy[i] < N and mapp[row][col] > mapp[row+dx[i]][col+dy[i]] and not visit[row+dx[i]][col+dy[i]]: # 맵 범위 벗어나는지, 다음칸이 지금보다 작은지, 방문하지 않았는지
            new_cnt = cnt + 1 # 등산로 길이를 늘려주고
            visit[row+dx[i]][col+dy[i]] = 1 # 다음칸 방문했음을 알림
            dfs(row+dx[i],col+dy[i],k,check,new_cnt) # 다시 dfs 탐색
            visit[row+dx[i]][col+dy[i]] = 0 # 백트래킹 후 방문배열 해제
        elif 0 <= row + dx[i] < N and 0 <= col + dy[i] < N and mapp[row][col] <= mapp[row+dx[i]][col+dy[i]] and check == 0 and not visit[row+dx[i]][col+dy[i]]: # 맵 범위 벗어나는지, 다음칸이 같거나 크다면 굴삭할껀데 이미 굴삭한 적 없고 방문하지 않아야함.
            for j in range(1,k+1): # 굴삭깊이 1~k만큼 파봄
                mapp[row+dx[i]][col+dy[i]] -= j # 판 깊이 만큼 높이 깎아줌
                if mapp[row][col] > mapp[row+dx[i]][col+dy[i]]: # 깎은 높이가 낮아져서 등산로로 활용할 수 있다면
                    visit[row+dx[i]][col+dy[i]] = 1 # 방문할꺼기에 방문배열 체크
                    new_cnt = cnt + 1 # 등산로 길이 1 올려주고
                    dfs(row+dx[i],col+dy[i],k-j,1,new_cnt) # 다시 다음 등산로를 탐색
                    visit[row+dx[i]][col+dy[i]] = 0 # 백트래킹 후 방문 배열 해제
                mapp[row+dx[i]][col+dy[i]] += j # 백트래킹 했으므로 깎은 산 높이도 정상화 시킴
    if max_cnt < cnt: # 4방향체크를 다하고 갈 곳이 없으면 max값과 비교 후 return
        max_cnt = cnt
    return
 
T = int(input())
for t in range(T):
    N, K = map(int,input().split())
    mapp = [list(map(int,input().split())) for _ in range(N)]
 
    max_arr = [] ## 최고 높이를 구하는 과정
    for i in range(N):
        max_arr.append(max(mapp[i]))
    maxx = max(max_arr)
 
    max_cnt = -9999999
 
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    visit = [[0 for _ in range(N)] for _ in range(N)] # 방문배열
    for y in range(N):
        for x in range(N):
            if mapp[x][y] != maxx: #최고 봉우리가 아니면 pass시킴
                continue
            visit[x][y] = 1 # 너무 중요하다... 첫 시작지점도 방문했음에 체크를 해줘야한다.
            dfs(x,y,K,0,1)
            visit[x][y] = 0
    print('#{} {}'.format(t+1,max_cnt))