매트릭스가 주어지고 해당 매트릭스 내에 최댓값(들)을 찾아 해당 지점에서 상하좌우 탐색을 하며 내리막길로 된 등산로를 조성하는 문제
- 최대 공사 가능깊이가 있고 이 깊이를 이용해 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))