[Python] SW Expert Academy #1949 등산로 조성

📚문제: #1949 등산로 조성(모의 SW 역량테스트)

전체 코드

# 1949. 등산로 조성
from copy import deepcopy

# 백트래킹 함수
def backtracking(c, G, l):
    
    global trail_len
    
    # 갱신
    trail_len = max(trail_len, l)
    
    # 이동가능한 4방향
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    # 현재 좌표
    cur_r, cur_c = c
    
    # 방문체크
    visited[cur_r][cur_c] = True
    
    # 4방향
    for i in range(4):
        
        move_r, move_c = cur_r + dr[i], cur_c + dc[i]
        
        # 주어진 범위를 벗어나지 않아야한다.
        if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
            
            # 이웃 봉우리가 더 낮은 위치면 등산로 조성 가능, 또한 아직 방문하지 않은 지점이어야한다.
            if G[move_r][move_c] < G[cur_r][cur_c] and not visited[move_r][move_c]:
                
                # 재귀 호출
                backtracking([move_r, move_c], G, l+1)
                
                # 방문체크 해제
                visited[move_r][move_c] = False

# 총 테스트 케이스 T
T = int(input())

# T개의 테스트 케이스
for t in range(1, T+1):
    
    # 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 주어진다.
    N, K = map(int, input().split())
    
    # 지도
    grid = []
    
    # 지도 정보가 주어진다.
    for _ in range(N):
        
        grid.append(list(map(int, input().split())))
    
    # 가장 높은 봉우리를 찾는다. 단 여러개 있을 수도 있다.
    max_height = -1
    for i in range(N):
        
        for j in range(N):
            
            # 갱신
            if grid[i][j] > max_height:
                
                max_height = max(max_height, grid[i][j])
    
    # 가장 높은 봉우리를 모두 찾는다.
    max_height_loc = []
    for i in range(N):
        
        for j in range(N):
            
            if grid[i][j] == max_height:
                
                max_height_loc.append([i,j])
                
    # 등산로 길이 초기화
    trail_len = -1
    
    # 최대 길이
    max_trail_len = -1
    
    # 봉우리를 깎지 않을 때 모든 케이스 진행
    for loc in max_height_loc:

        visited = [[False] * N for _ in range(N)]
        
        backtracking(loc, grid, 1)
        
        max_trail_len = max(max_trail_len, trail_len)
        
        trail_len = -1
 
    # 봉우리를 깎을 때 모든 케이스 진행
    for loc in max_height_loc:

        # 시작 봉우리
        s_r, s_c = loc
        
        for i in range(N):
            
            for j in range(N):
                
                # 시작 봉우리와 깎는 위치가 같지 않을때만 실행, 같으면 skip
                if s_r == i and s_c == j:
                    
                    continue
                
                else:
                    
                    for drill in range(1, K+1):
                        
                        # 복사
                        grid_temp = deepcopy(grid)
                        
                        grid_temp[i][j] -= drill
                        
                        if grid_temp[i][j] < 0:
                            
                            grid_temp[i][j] = 0
                        
                        # 방문여부 리스트
                        visited = [[False] * N for _ in range(N)]
                        
                        # 함수 실행
                        backtracking(loc, grid_temp, 1)
                        
                        # 갱신
                        max_trail_len = max(max_trail_len, trail_len)
                        
                        # 초기화
                        trail_len = -1
    
    # 답안 출력
    print("#{} {}".format(t, max_trail_len))

아이디어

어떠한 봉우리도 깎지 않거나, 가장 높은 봉우리를 제외한 모든 지점에서 1 ~ K만큼 깎은 후 백트래킹 알고리즘을 적용해준다. 이동할 수 있는 지점은 이동 후 방문처리, 더 이상 이동할 수 없을 때는 해당 지점을 반드시 방문해제해준다.