1949. 등산로 조성 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

def dfs(length,s,chance):
    global max_length
    max_length=max(max_length,length)
    r,c=s[:]
    dr=[1,0,-1,0]
    dc=[0,1,0,-1]
    for i in range(4):
        nr=r+dr[i]
        nc=c+dc[i]
        if 0<=nr<N and 0<=nc<N and not visited[nr][nc] and maps[nr][nc]-K<maps[r][c]:
            if maps[nr][nc]<maps[r][c]:
                visited[nr][nc]=True
                dfs(length+1,[nr,nc],chance)
                visited[nr][nc]=False
            elif chance:
                visited[nr][nc]=True
                tmp=maps[nr][nc]
                maps[nr][nc]=maps[r][c]-1
                dfs(length+1,[nr,nc],chance-1)
                maps[nr][nc]=tmp
                visited[nr][nc]=False
         
 
T = int(input())
 
for test_case in range(1, T + 1):
    N,K=map(int,input().split())
    maps=[]
    max_h=0
    for _ in range(N):
        tmp_list=list(map(int,input().split()))
        maps.append(tmp_list)
        max_h=max(max_h,max(tmp_list))
    max_h_list=[]
    for i in range(N):
        for j in range(N):
            if maps[i][j]==max_h:
                max_h_list.append([i,j])
    ans_list=[]
    for mh in max_h_list:
        max_length=0
        visited=[[False]*N for _ in range(N)]
        visited[mh[0]][mh[1]]=True
        dfs(0,mh,1)
        ans_list.append(max_length)
    ans=max(ans_list)+1
    print(f'#{test_case} {ans}')

• 가장 높은 지점의 높이를 찾고, 그 높이에 해당하는 모든 좌표를 찾는다.
• 해당 좌표들에서 모두 dfs를 적용한다.
• dfs를 적용할 때, chance란 K만큼 땅을 팔 수 있는 기회를 의미한다. 즉 1일때만 사용할 수 있다.
• 만약 탐색하려는 지점이 visited하지 않고, map영역 안에 있다면 기본 요건을 만족한 것이다.
• 가장 중요한 요건은 현재 높이보다 낮은가인데, 이때 탐색 지점의 높이-K가 현재 높이보다 작으면 1차 조건을 달성한 것으로 하고, K만큼 줄이지 않아도 만족할 때와 K만큼 줄여야만 만족하는 경우를 나눠서 dfs를 돌린다.
• K만큼 줄여야 할 경우 chance가 아직 1인 경우에만 탐색을 한다. chance-1을 넣고 (chance는 0이 된다) 다음 영역의 높이는 현재보다 1작은 값을 넣어준다. (높이가 높을수록 등산로의 길이가 가장 길어질 가능성이 높기 때문이다. 탐색지점높이-K보다 현재 높이-K가 항상 크거나 같다.)