SW Expert Academy - 등산로 조정 (python)

❓ 문제 - SW Expert Academy 등산로 조정 python 풀이법

 

출처 

(https://swexpertacademy.com/main/solvingProblem/solvingProblem.do)

SW Expert Academy

 

 

 

 

📝 문제해결법

1. 이 문제는 DFS + 구현으로 풀었다.

• 일단 가장 높은 봉우리를 찾고, 모든 행과 열 돌면서 가장 높은 봉우리랑 값이 같다면 dfs를 돌아서 등산로 길이의 최대값을 갱신해야한다.
• 4방향으로 돌면서 범위 안이고 만약 방문한 적이 없을 때, 가려는 곳이 현재 봉우리 높이보다 낮다면 해당 곳으로 방문처리 후 재귀로 들어간다. 현재 봉우리 높이 조정을 하지 않은 상태라면(flag = True) 만약 현재 봉우리 높이와 동일하거나 크다면 1 ~ k까지의 중의 현재봉우리와 이동하려는 봉우리의 차이 +1 보다 크면 파준 후, DFS 재귀로 들어가서 등산로길이를 만든다.

2. 이 문제는 DFS + 구현으로 풀었다.

• 처음에 BFS로 풀려서 덤비다가, 이게 DFS구나 깨달았다... 앞으로 문제 풀 때, DFS, BFS 구분 확실히 해서 접근해야겠다...
• 그리고 봉우리 높이 조정할 때 무조건 현재 봉우리와 이동할 봉우리의 높이 값의 차이 +1 만큼만 해줄 필요없이 모든 경우의 수를 탐색할 수 있도록 조정해야한다...

 

 

💻 소스코드

T = int(input())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(depth, x, y, val, flag):
    global max_leng
    if max_leng < depth:
        max_leng = depth

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == False:
            if board[nx][ny] < val:
                visited[nx][ny] = True
                dfs(depth+1, nx, ny, board[nx][ny], flag)
            else:
                if flag:
                    for c in range(1, k+1):
                        if (board[nx][ny]-val+1) <= c and (board[nx][ny]-c) >= 0:
                            visited[nx][ny] = True
                            dfs(depth+1, nx, ny, board[nx][ny]-c, False)
            visited[nx][ny] = False
    return

for test_case in range(1, T+1):
    n, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    max_leng = 0
    max_value = 0
    for i in range(n):
        max_value = max(max_value, max(board[i]))
    visited = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if board[i][j] == max_value:
                visited[i][j] = True
                dfs(1, i, j, max_value, True)
                visited[i][j] = False

    print(f'#{test_case} {max_leng}')