[코딩테스트][SWEA] 🔥 SWEA 1949번 "등산로 조성" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 40분

from collections import deque

dx=[0,0,-1,1]
dy=[-1,1,0,0]

def dfs(x,y,deep):
    global longestLoad
    longestLoad=max(longestLoad,deep)
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if nx<0 or ny<0 or nx>=N or ny>=N:
            continue
        if board[nx][ny]>=board[x][y]:
            continue
        dfs(nx,ny,deep+1)

for tc in range(1,int(input())+1):
    N,K=map(int,input().split())
    maxH=0
    maxHList=[]
    board=[]
    for i in range(N):
        arr=list(map(int,input().split()))
        for j in range(N):
            if arr[j]>maxH:
                maxH=arr[j]
                maxHList=[]
                maxHList.append((i,j))
            elif arr[j]==maxH:
                maxHList.append((i,j))
        board.append(arr)
    longestLoad=1
    for i in range(N):
        for j in range(N):
            for k in range(0,K+1):
                board[i][j]-=k
                for x,y in maxHList:
                    dfs(x,y,1)
                        
                board[i][j]+=k
    print("#"+str(tc)+" "+str(longestLoad))

최고의 등산로: K만큼 산을 깎아라! 🏔️⛏️

등산로를 만들 수 있는 최대 길이를 구하되 K만큼 1회 산을 깎을 수 있는 경우를 사용할 수 있는 문제이다. DFS로 풀 수 있으면서 완전탐색을 사용하였다.

각 최고점에 대해서 밑으로 내려것만이 등산로를 이룰 수 있으므로 가장 최고점의 좌표를 전부 찾는다. 그리고 모든 지점에 대해서 0~K까지 높이를 깎아보면서 각 최고점에서의 DFS를 수행하면 된다. 이 때 현재 위치보다 낮은 위치로만 DFS를 수행하면 된다. 이 때의 최대 깊이를 갱신하여 출력하면 된다.

이렇게 Python로 SWEA의 "등산로 조성" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊