🥚문제링크

https://www.acmicpc.net/problem/1937

• 다이나믹 프로그래밍
• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

---

🍳코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input().strip())
arr = [list(map(int, input().split())) for _ in range(n)]

# dp[r][c] = (r, c)에서 갈 수 있는 최대 칸 수
# 방문하지 않았을 때는 0으로 초기화
dp = [[0]*n for _ in range(n)]


def dfs(r, c):
    # 방문 기록이 있으면 return
    if dp[r][c] != 0:
        return dp[r][c]

    # 방문 기록이 없으면 1
    if dp[r][c] == 0:
        dp[r][c] = 1

    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]
    for i in range(4):
        nr = r + dr[i]
        nc = c + dc[i]
        if 0 <= nr < n and 0 <= nc < n:
            if arr[r][c] < arr[nr][nc]:
                dp[r][c] = max(dp[r][c], dfs(nr, nc) + 1)

    return dp[r][c]


ans = 0
for r in range(n):
    for c in range(n):
        ans = max(ans, dfs(r, c))

print(max(map(max, dp)))

---

🧂아이디어

DP, DFS

유사한 문제 풀이: [백준 1890] 점프 ❕ | [백준 1520] 내리막 길 ❗

• DFS로만 풀면 시간초과

• DP + DFS로 풀이해야 한다. 비슷한 풀이방식으로는 위에 링크해 둔 두 문제가 있다.

• dp[r][c] = (r, c)에서 갈 수 있는 최대 칸 수

• dp[r][c]는 방문한 적이 없으면 0으로 초기화

• dfs(r, c)를 하며 (r, c)에 방문한 적이 있으면 dp[r][c]를 리턴한다.

• dfs(r, c)를 하며 (r, c)에 방문한 적이 없으면 dp[r][c] = 1로 갱신한다.

• 이후, 상 하 좌 우를 탐색하며 현재 칸보다 다음에 이동할 칸에 대나무가 많으면 dp[r][c] = max(dp[r][c], dfs(nr, nc) + 1)로 값을 갱신한다.