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

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

SW Expert Academy

 

1️⃣ 등산로는 가장 높은 봉우리에서 ➡️ Max 값 구해주고, 이중 for문으로 Max값과 같다면 dfs 돌려주기

2️⃣ 가로 or 세로로 이동, 높은 → 낮은 ➡️ 상 하 좌 우, Branch 4

3️⃣ 딱 한 곳을 정해 최대 공사 가능 깊이 K만큼 ➡️ 처음에 K보다 작으면 등산로를 조성할 수 없다고 이해했는데, 문제 풀면서 잘못 이해했다는 것을 깨달았다.

4️⃣ 만들 수 있는 가장 긴 길이 ➡️ Max_length

 

💥 주의

• 최대 공사 가능 깊이 K는 K만큼 깎을 수 있다는 뜻이다. 가령, 8인 산을 깎으려 하고 K가 3이라면 5까지만 깎을 수 있는 것이다.

 

def dfs(y, x, nowheight, cnt, check):
    global Max_length
    directy = [-1, 1, 0, 0]
    directx = [0, 0, -1, 1]
    for i in range(4):
        dy = directy[i]+y
        dx = directx[i]+x
        if 0 <= dy < N and 0 <= dx < N:
            if visit[dy][dx] == 1:continue # 방문한 적 있으면 X
            if mountain[dy][dx] < nowheight: # 이동하려는 산의 높이가 현재 산의 높이보다 작으면
                visit[dy][dx] = 1
                dfs(dy, dx, mountain[dy][dx], cnt+1, check)
                visit[dy][dx] = 0
            else:
                # 이동하려는 산의 높이에서 현재 산의 높이를 뺀 값이 최대 공사 가능 깊이보다 작아야 뺐을 때 이동 가능
                if mountain[dy][dx]-nowheight < depth: 
                    if check != 1: # 판 적 없으면
                        visit[dy][dx] = 1
                        dfs(dy, dx, nowheight-1, cnt+1, 1)
                        visit[dy][dx] = 0

    if Max_length < cnt: # 더 이상 등산로를 공사할 수 없으면
        Max_length = cnt # 최대 길이 비교 및 갱신
    return

t = int(input())
for tc in range(1, t+1):
    N, depth = map(int, input().split()) # 한 변의 길이, 최대 공사 가능 깊이
    mountain = [list(map(int, input().split())) for _ in range(N)]
    visit = [[0]*N for _ in range(N)]
    Max = -2e18
    Max_length = -2e18
    # Max 값 찾아주기
    for i in range(N):
        Max = max(Max, max(mountain[i]))
    # Max와 같으면 dfs 돌려줌
    for y in range(N):
        for x in range(N):
            if mountain[y][x] == Max:
                visit[y][x] = 1
                dfs(y, x, mountain[y][x], 1, 0) # y, x, 현재 높이, 길이, 깎았는지
                visit[y][x] = 0
    print(f'#{tc} {Max_length}')