[BOJ] 욕심쟁이 판다 (1937, G3)

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

 

이 문제, 보기와 다르게 절대 쉽지 않습니다.

 

 

 

생각해본 방향

우선 가장 쉽게 생각해볼 수 있는 풀이는 다음과 같습니다.

"이거 그냥 DFS나 BFS 모든 점에서 하면 되는거 아님?"

저는 조금 더 현명하게 하기 위해 다음과 같이 약간 그리디하게 생각해 보았습니다.

시작점의 후보는 더 큰쪽으로 나가게 방향 그래프로 그리면 indegree =0 인 지점이다.

그렇게 dfs를 돌리면 된다! 선언을 하고 코드를 작성합니다.

# 아예 그래프를 만들어서 indegree가 0인 애를 찾아줘야 한다.
import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mv_list = [[1, 0], [-1, 0], [0, 1], [0, -1]] # D U R L

N = int(input())
forest = []
for _ in range(N):
    forest.append(list(map(int, input().split())))
indegree_cnt = [[0 for _ in range(N)] for _ in range(N)]
graph = [[[] for _ in range(N)] for _ in range(N)]
max_cnt = 0

# 방문 여부는 대소 비교의 특성상 담지 않아도 되려나?
def dfs(x, y, cur_level):
    global max_cnt
    if max_cnt < cur_level:
        max_cnt = cur_level
    for nx, ny in graph[x][y]:
        dfs(nx, ny, cur_level + 1)

# step 1.  그래프와 차수를 정보를 가져와야 한다.
for i in range(N):
    for j in range(N):
        for mv in mv_list:
            nx, ny = i + mv[0], j + mv[1]
            if 0 <= nx < N and 0 <= ny < N:
                # 주의! 양방향 비교가 아닌 한 쪽 방향만 비교해야 한다.
                if forest[i][j] > forest[nx][ny]:
                    indegree_cnt[i][j] += 1
                    graph[nx][ny].append((i, j))

# step 2. indegree 0인 지점에서 출발한다.
start_pos = []
for i in range(N):
    for j in range(N):
        if indegree_cnt[i][j] == 0:
            dfs(i, j, 1)
print(max_cnt)

 

 

하지만 이러면 실패!  시간초과나 bfs 버전의 경우는 메모리 초과 등이 발생합니다.  왜???

10
1 2 3 4 5 6 7 8 9 10
20 19 18 17 16 15 14 13 12 11
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
50 49 48 47 46 45 44 43 42 41
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
80 79 78 77 76 75 74 73 72 71
81 82 83 84 85 86 87 88 89 90
1 99 98 97 96 95 94 93 92 91

 

다음과 같은 케이스에서 예를 들어서 20 지점을 고려해봅시다. 1에서20을 바로 갈지... 1 2 19 20일지...

경우가 너무 많습니다! 방문 체크를 넣지 않아야 돌아가는 경우를 체크할 수 있다 판단했으나, 오판입니다.

결국 항복을 하고 답안지를 봤습니다. 그런데

 

ㄴㅇㄱ

 

의도 풀이

 

이 문제는 무려 DP + DFS 입니다!

dp에 -1을 해놓고, 최초의 방문일 경우 1로 초기화 합니다. 그 이후, 그것보다 더 작은 칸에 가면 현재 dp값을 바꿔줍니다만... 그 것보다 더 작은 칸에서 더 작은게 발생...발생... 이의 최댓값을 모두 가져오려면.....  

재귀적으로 호출해가며 dp를 갱신합니다. 방문 체크 여부는 최초 방문 체크용 + 최댓값 검수용 입니다. 최초 방문이 아닐 때에는 그 칸에서 계산할 이유가 1도 없습니다. 이미 다른 칸의 경로도 계산이 끝났고, 전혀 다른 칸에서의 계산은 그 때 가서 계산이 될 거라 문제가 없습니다.

# dfs, bfs로만 풀면 시간 초과나 메모리 초과가 발생한다.
# DP + DFS를 하는 방법을 배워보자.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mv_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def dfs(cx, cy):
    # 순환은 발생하지 않으나, 방문 반복 체크를 막기 위함
    if dp[cx][cy] != -1:
        return dp[cx][cy]

    dp[cx][cy] = 1
    for mv in mv_list:
        nx = cx + mv[0]
        ny = cy + mv[1]
        if 0 <= nx < N and 0 <= ny < N:
            if forest[nx][ny] > forest[cx][cy]:
                # 한칸 더 갈 수 있으면, 그 깊이를 +1 +1 ..해서 저장한다.
                # 이거 자체가 경로를 기억하는 효과가 있어 돌아오는 거마다 -1씩 까인다.
                dp[cx][cy] = max(dp[cx][cy], dfs(nx, ny) + 1)
    return dp[cx][cy]


N = int(input())
forest = []
for _ in range(N):
    forest.append(list(map(int, input().split())))

dp = [[-1 for _ in range(N)] for _ in range(N)]
answer = 0

for i in range(N):
    for j in range(N):
        answer = max(answer, dfs(i, j))
print(answer)

 

처음보는 DFS + DP 활용이었습니다. 이런 식으로...발상할 수 있다는 점이 놀라웠고, 역시 DFS에서 방문 체크를 하는 이유를 다시 체감하게 됩니다.