이 포스팅은 다시 풀 문제들 시리즈 5 편 중 3 번째 글 입니다.
목차
골드3 : dp? 문제이다.
풀이
음..풀이를 이상하게 했는지는 모르겠지만 일단 맞았다.
다른 사람들을 보니, 각각의 시작 위치에서 dfs를 돌려서 최대 거리를 구한뒤 max 를 취하는 방법을 사용한 것 같았다. 이렇게 풀었어도 될 걸 이상하게 풀었다.
일단 내 풀이는, 일단 dp를 정의했다.
dp[i][j] = 해당 나무까지 포함했을 때, 최대 생존 길이
dp[i][j] = 상하좌우에서 오는 생존거리 + 1 (물론 올 수 있을 때)
이렇게 정의를 하니 일단 풀리긴 풀리더라. 그래서 처음 map에서 이 방법을 시도했는데, 결국 dp는 이전의 작은 해답이 다음 해답을 찾을 수 있어야 했는데, 순차적으로 위의 방법을 진행하니 당연히 실패했다.
그래서 작은 값, 즉 나무가 적은 곳에서 부터, 해당 위치를 포함했을 때 생존길이가 얼마인지를 업데이트하면서 전체 위치에서의 생존 길이를 구했다.
어떻게 보면 dfs는 탑다운 방식, 내 방법은 바텀업 방식이라고 할 수 있을 것 같다.
배워야 하는 점은, dfs 를 여러번 사용해서 답을 구할 수 있다는 것. 예전에 카카오 문제를 풀었을 때나, 트리의 최대 지름같은 문제를 풀 때도 그러했다. 이제는 각각의 알고리즘을 모듈화해서 엮을 정도의 실력이 되어야 한다.
Code
import sys
from pprint import pprint
from itertools import chain
input = sys.stdin.readline
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[1 for _ in range(n)] for _ in range(n)]
d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
order = []
for i in range(n):
for j in range(n):
order.append([graph[i][j], [i, j]])
order.sort()
for o in order:
trees, coord = o
cy, cx = coord
for (
dy,
dx,
) in d:
ny, nx = cy + dy, cx + dx
if 0 <= ny < n and 0 <= nx < n and trees > graph[ny][nx]:
visited[cy][cx] = max(visited[cy][cx], visited[ny][nx] + 1)
print(max(list(chain(*visited))))