SWEA-1949-등산로 조성

매트릭스가 주어지고 해당 매트릭스 내에 최댓값(들)을 찾아 해당 지점에서 상하좌우 탐색을 하며 내리막길로 된 등산로를 조성하는 문제

• 최대 공사 가능깊이가 있고 이 깊이를 이용해 1번 현재 지점보다 높은 지점을 공사하여 등산로를 조성할 수 있음

• 최적화 문제이기 때문에 완전탐색을 해야겠다고 생각
• 최장경로를 찾기 위해 BFS를 가장 먼저 떠올림
• BFS로 구현 시 백트래킹이 되지 않아 방문정보 표시가 번거로움
• DFS로 변경

DFS

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # 상하좌우 델타 탐색을 위한 리스트


def dfs(info): # 재귀를 이용한 DFS
    global MAX, V
    r, c, h, k, d = info # 현재 지점의 row 좌표, col 좌표, 해당 지점의 높이, 해당 지점에서 공사 가능 깊이, 현재 까지 공사를 진행한 길이

    if d > MAX: # 함수 진입 시 등산로의 길이를 최장경로로 갱신
        MAX = d

    for i in range(4):
        dr, dc = r + dx[i], c + dy[i]
        if 0 <= dr < N and 0 <= dc < N and not V[dr][dc]: # 탐색하는 곳이 방문하지 않았던 곳이고 지도 범위에 벗어나지 않을 때
            dh = M[dr][dc]  # 등산로를 조성하려는 곳의 높이
            if dh < h:  # 등산로를 조성하려는 곳의 높이가 현재 높이보다 작다면
                V[dr][dc] = True # 방문 체크
                dfs([dr, dc, dh, k, d+1]) # 재귀를 이용한
                V[dr][dc] = False # 방문 해제 (이렇게 함으로 인해 하나의 방문리스트를 이용해 중복되지 않는 경로를 탐색 가능)
            elif h <= dh < h + k:  # 등산로를 조성하려는 곳의 높이가 현재 높이보단 크지만 공사를 하면 현재 높이보다 낮출 수 있다면
                V[dr][dc] = True # 방문 체크
                dfs([dr, dc, (h-1), 0, d+1])
                V[dr][dc] = False # 방문 해제 (이렇게 함으로 인해 하나의 방문리스트를 이용해 중복되지 않는 경로를 탐색 가능)


for T in range(1, int(input())+1):
    N, K = list(map(int, input().split())) # 지도의 한 변의 크기, 공사 가능 깊이
    M = [] # 지도를 담을 리스트
    TOP, MAX = 0, 0  # 가장 높은 봉우리의 값, 최장 등산로 길이
    V = [[False for _ in range(N)] for _ in range(N)] # 이미 공사한 곳을 재방문 하지 않도록 할 visit 리스트

    # 가장 높은 봉우리를 찾기, 그리고 지도 입력값 받기
    for _ in range(N):
        temp = list(map(int, input().split()))
        if max(temp) > TOP:
            TOP = max(temp)
        M.append(temp)

    # 지도를 순회하면서 가장 높은 봉우리(들을)를 찾고 해당 좌표에서 깊이우선탐색을 하여 최장 등산로를 찾을 것임
    for row in range(N):
        for col in range(N):
            if M[row][col] == TOP:
                V[row][col] = True
                temp = dfs([row, col, TOP, K, 1]) # 해당 좌표에서 시작한 등산로 중 가장 긴 경로를 MAX 변수에 갱신함
                V[row][col] = False

    print('#{} {}'.format(T, MAX))

BFS

from collections import deque
import copy


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


def bfs(info):
    queue = deque() # 속도를 위해 do
    queue.append(info)
    result = 0

    while queue:
        r, c, v, k, l, visit = queue.popleft()
        # row 좌표, col 좌표, 현재 땅의 높이, 현재까지 진행한 길이, 현재까지 진행한 visit 리스트
        for i in range(4):
            dr, dc = r + dx[i], c + dy[i] # delta row, delta col 좌표
            if 0 <= dr < N and 0 <= dc < N and visit[dr][dc]: # 델타 좌표가 지도를 벗어나지 않는 범위에 있고 이미 등산로를 조성한 좌표가 아닐 때!
                dv = M[dr][dc] # 등산로를 조성하려는 곳의 높이
                if dv < v: # 등산로를 조성하려는 곳의 높이가 현재 높이보다 작다면
                    # DFS는 백트래킹이 가능하므로 하나의 visit을 계속해서 사용할 수 있지만 BFS의 경우 이러한 방식으로 이미 공사를 한 등산로의 중복을 막아야 함
                    tv = copy.deepcopy(visit)
                    tv[dr][dc] = False # 방문 체크
                    queue.append([dr, dc, dv, k, l+1, tv]) # 큐에 공사할 등산로 지점 정보를 추가
                    if l+1 > result:
                        result = l+1
                elif v <= dv < v + k: # 등산로를 조성하려는 곳의 높이가 현재 높이보단 크지만 공사를 하면 현재 높이보다 낮출 수 있다면
                    tv = copy.deepcopy(visit)
                    tv[dr][dc] = False # 방문 체크
                    queue.append([dr, dc, (v-1), 0, l+1, tv])
                    if l+1 > result:
                        result = l+1
    return result


for T in range(1, int(input())+1):
    N, K = list(map(int, input().split())) # 지도의 한 변의 크기, 공사 가능 깊이
    M = [] # 지도를 담을 리스트
    MAX = 0 # 가장 높은 봉우리의 값
    result = 0 # 최장 경로의 등산로 길이
    V = [[True for _ in range(N)] for _ in range(N)] # 이미 공사한 곳을 재방문 하지 않도록 할 visit 리스트

    # 가장 높은 봉우리를 찾기, 그리고 지도 입력값 받기
    for _ in range(N):
        temp = list(map(int, input().split()))
        if max(temp) > MAX:
            MAX = max(temp)
        M.append(temp)

    # 지도를 순회하면서 가장 높은 봉우리(들을)를 찾고 해당 좌표에서 너비우선탐색을 하여 최장 등산로를 찾을 것임
    for row in range(N):
        for col in range(N):
            if M[row][col] == MAX:
                V[row][col] = False
                temp = bfs([row, col, MAX, K, 1, V]) # 해당 좌표에서 시작한 등산로 중 가장 긴 경로를 반환
                V[row][col] = True
                if result < temp:
                    result = temp
    print('#{} {}'.format(T, result))