욕심쟁이 판다 (1937번) - 백준 (BOJ)

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

1937번: 욕심쟁이 판다

 

 

백준 - 욕심쟁이 판다 (1937번)

 

난이도 : Gold 3

알고리즘&자료구조 : DFS (깊이 우선 탐색) & Dynamic Programming (동적계획법, DP)

풀이 소요시간 : 25분

 

 

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


def adjs(r, c):
    if 0 < r:  yield r-1, c
    if 0 < c:  yield r, c-1
    if r < n-1:  yield r+1, c
    if c < n-1:  yield r, c+1


def dfs(r, c):
    maxy = 0
    for rr, cc in adjs(r, c):
        if forest[rr][cc] <= forest[r][c]:
            continue
        if memo[rr][cc]:
            maxy = max(maxy, memo[rr][cc])
        else:
            maxy = max(maxy, dfs(rr, cc))
    memo[r][c] = maxy + 1
    return memo[r][c]


if __name__ == '__main__':
    n = int(input())
    forest = [list(map(int, input().split())) for _ in range(n)]
    memo = [[0]*n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            if memo[r][c]:
                continue
            dfs(r, c)
    print(max(max(r) for r in memo))

 

 

DFS와 DP를 활용하는 문제이다.

 

(1, 1) 칸부터 (n, n) 칸까지 하나씩 확인하면서

이전에 해당 칸에 dfs를 통해 방문한 적이 없다면,

해당 칸에 dfs 함수를 적용한다.

 

 

▶ dfs 함수

 

dfs 함수는, 입력받은 칸에 대해서 상하좌우 인접칸들을 탐색한다.

 

인접칸의 값이 입력칸보다 작거나 같다면, 판다가 이동할 수 없기 때문에 그냥 넘어간다.

 

값이 입력칸보다 큰 나머지 인접칸들 중, 가장 큰 memo 값을 가져와서 1을 더하고

memo[입력칸] = (인접칸 중 가장 큰 값 + 1) 로 업데이트 한다.

(만약 인접칸의 memo 값이 0이라면, dfs로 방문한 적이 없으므로

해당 칸에 dfs 함수를 적용해서 memo 값을 업데이트 해준다.)

 

만약 입력칸보다 큰 인접칸이 없다면,

memo[입력칸] = 1 이 된다.

 

 

출력

 

memo에서 가장 큰 값을 출력하면, 그것이 정답이다.