[SWEA 1949] 등산로 조성

접근

최대 높이를 찾고 2차원 맵을 탐색해서 최대 높이의 위치에서 DFS를 진행한다. 현재 위치에서 상하좌우 탐색을 진행하고 현재 위치보다 높이가 작은 위치로 이동한다. 만약 같거나 클 때는 K만큼 공사할 수 있는지 판단하여 이동한다.

 

구현

- 최대 높이를 찾아서 max_value에 저장한다.

- 2차원 리스트인 board를 탐색해서 max_value가 나올 때마다 dfs를 진행한다.

- dfs에는 현재 위치, 방문 여부, 길이, 공사의 여부를 전달한다.

    N, K = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]

    max_value = 0
    for y in range(N):
        for x in range(N):
            if board[y][x] > max_value:
                max_value = board[y][x]


    answer = 0
    visited = [[False for _ in range(N)] for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if board[y][x] == max_value:
                dfs(y, x, visited, 1, 0)

 

- 먼저 방문한 현재 위치를 방문 표시한다.

- 이후 현재 위치를 기준으로 상하좌우 탐색을 진행한다.

- 먼저 다음 위치가 현재 위치보다 작을 때 진행한다.

- 또한 현재 위치보다 크거나 같을 때는 공사를 할 수 있는지 판단하여 다음 위치에 최소로 높이를 깎도록 공사한다.

- 만약 상하좌우가 모두 진행할 수 없다면 현재까지의 step으로 최댓값을 비교한다.

def dfs(y, x, visited, step, flag):
    global answer
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    visited[y][x] = True
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx) and visited[ny][nx] == False:
            if board[ny][nx] < board[y][x]:
                visited[ny][nx] = True
                dfs(ny, nx, visited, step+1, flag)
                visited[ny][nx] = False
            if flag == 0 and board[ny][nx] >= board[y][x] and board[ny][nx] - board[y][x] + 1 <= K:
                visited[ny][nx] = True
                height = board[ny][nx]
                board[ny][nx] = board[ny][nx] - (board[ny][nx] - board[y][x] + 1)
                dfs(ny, nx, visited, step+1, 1)
                visited[ny][nx] = False
                board[ny][nx] = height

    answer = max(answer, step)
    visited[y][x] = False

---

전체 코드

test_case = int(input())


def check_range(y, x):
    return (0 <= y < N) and (0 <= x < N)

def dfs(y, x, visited, step, flag):
    global answer
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    visited[y][x] = True
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx) and visited[ny][nx] == False:
            if board[ny][nx] < board[y][x]:
                visited[ny][nx] = True
                dfs(ny, nx, visited, step+1, flag)
                visited[ny][nx] = False
            if flag == 0 and board[ny][nx] >= board[y][x] and board[ny][nx] - board[y][x] + 1 <= K:
                visited[ny][nx] = True
                height = board[ny][nx]
                board[ny][nx] = board[ny][nx] - (board[ny][nx] - board[y][x] + 1)
                dfs(ny, nx, visited, step+1, 1)
                visited[ny][nx] = False
                board[ny][nx] = height

    answer = max(answer, step)
    visited[y][x] = False


for tc in range(test_case):
    N, K = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]

    max_value = 0
    for y in range(N):
        for x in range(N):
            if board[y][x] > max_value:
                max_value = board[y][x]


    answer = 0
    visited = [[False for _ in range(N)] for _ in range(N)]
    for y in range(N):
        for x in range(N):
            if board[y][x] == max_value:
                dfs(y, x, visited, 1, 0)

    print("#{} {}".format(tc+1, answer))