[SWEA] 1949. 등산로 조성 (python)

문제풀이

• dfs를 이용하여 최적화를 하는 문제이다.
• 가장 높은 봉우리에서 부터 탐색을 시작함.
  • 봉우리의 사방을 탐색
  • 다음 길이 낮으면 그대로 탐색 진행(dfs호출)
  • 다음 길의 높이가 같거나 높고 공사를 아직 안했으면 공사를 진행함
    • 공사는 최대 깊이 K만큼 할 수 있음 (1~K)
    • 모든 경우( 모든 공사깊이 ) 를 탐색
    • 공사 후에 다음 길의 높이가 낮아졌다면 dfs를 호출해서 탐색 계속 (dfs호출)
  • 등산로길이의 최대값을 계속 업데이트해서 최대값을 결과로 얻음

소스코드(python)

dr = [-1,0,1,0]
dc = [0,1,0,-1]
def dfs(r,c,path,isConst):
    global ans
    if ans < path:  #최장 등산로 갱신하기
        ans = path
    #사방 탐색 : 등산로 탐색
    for k in range(4):
        nr = r + dr[k]
        nc = c + dc[k]
        if nr <0 or nr >= N or nc < 0 or nc >= N : continue #영역벗어나면 스킵
        if visited[nr][nc] == 1 : continue
        #이동가능하면 이동
        if m[r][c] > m[nr][nc] :
            visited[nr][nc] = 1
            dfs(nr,nc,path+1,isConst)
            visited[nr][nc] = 0
        #이동이 불가능하고 공사를 아직 안했으면 (1~K만큼 공사 가능 -> 모든경우)
        elif m[r][c] <= m[nr][nc] and not isConst:
            for i in range(1,K+1):
                m[nr][nc] -= i  #공사하기
                isConst = True
                if m[r][c] > m[nr][nc]:
                    visited[nr][nc] = 1
                    dfs(nr,nc,path+1,isConst)
                    visited[nr][nc] = 0
                #공사 취소하기 -> 다른 경우를 체크하기 위해
                isConst = False
                m[nr][nc] += i

T = int(input())
for tc in range(1,T+1):
    N,K = map(int,input().split())
    m = [ list(map(int,input().split())) for _ in range(N)]
    #가장 높은 봉우리 찾기
    maxH = 0
    for i in range(N):
        for j in range(N):
            if maxH < m[i][j] :
                maxH = m[i][j]
    ans = 0
    for i in range(N):
        for j in range(N):
            if m[i][j] == maxH:
                visited = [[0]*N for _ in range(N)]     #방문배열
                visited[i][j] = 1
                dfs(i,j,1,False)   #좌표,등산로길이,공사여부

    print("#{} {}".format(tc,ans))