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

문제 바로가기 : [모의 SW 역량 테스트] 탈주범 검거

SW Expert Academy

문제 요약

• 높은곳에서 낮은 곳으로 가로 또는 세로 방향으로 연결되는 최대 등산로의 길이를 구하는 문제
• 최대 K만큼 한번 깎을 수 있다.

def dfs(x, y, cnt, k_cnt):
    global max_cnt
    # 최댓값 갱신
    if max_cnt < cnt:
        max_cnt = cnt
    visited[y][x] = 1
    # 4방향 탐색 하면서
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위 내에 있으면 들어간다
        if 0 <= nx < N and 0 <= ny < N and visited[ny][nx] == 0:
            # 더 낮은 경우에만 들어가서 cnt값 +1 해줌
            if arr[ny][nx] < arr[y][x]:
                visited[ny][nx] = 1
                dfs(nx, ny, cnt+1, k_cnt)
                visited[ny][nx] = 0
            # 같거나 높은 경우에
            else:
                # K만큰 깎았을 때 지나갈 수 있는지 확인
                if arr[ny][nx] - arr[y][x] < K:
                    # 깎을 수 있는 횟수가 남았다면
                    if k_cnt == 1:
                        a = arr[ny][nx] - arr[y][x] + 1
                        arr[ny][nx] -= a
                        visited[ny][nx] = 1
                        dfs(nx, ny, cnt+1, k_cnt-1)
                        visited[ny][nx] = 0
                        arr[ny][nx] += a


T = int(input())
for tc in range(1, T+1):
    N, K = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]

    # 4방향 탐색
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    # dfs를 시작할 가장 높은 값을 구한다.
    max_h = 0

    for i in range(N):
        for j in range(N):
            if arr[i][j] > max_h:
                max_h = arr[i][j]

    max_cnt = 0
    # 깍을 수 있는 횟수
    k_cnt = 1

    for i in range(N):
        for j in range(N):
            if arr[i][j] == max_h:
                visited = [[0] * N for _ in range(N)]
                # 가장 높은 봉우리에서 bfs 시작
                dfs(j, i, 1, 1)

    print('#{} {}'.format(tc, max_cnt))

총평

기본 bfs문제에서 딱 한가지 응용력을 요하는 문제.

bfs의 흐름을 잘 이해한다면 어렵지 않게 풀 수 있는 문제인것 같다.