[알고리즘 문제 풀이][파이썬] 백준 1937번: 욕심쟁이 판다

백준 1937 문제 링크: https://www.acmicpc.net/problem/1937

📑 문제 설명
1. n x n 크기의 대나무숲이 있음
2. 각 칸에는 대나무의 양이 표시되어 있음
3. 판다는 특정 칸에서 대나무를 먹기 시작하며 상하좌우로 움직을 수 있으나 현재 위치보다 다음 위치에 있는 대나무의 양이 더 많아야 함

입력: 첫째 줄에는 n의 크기가 주어지고 둘째 줄부터 대나무 숲의 정보가 주어짐
출력: 판다가 이동할 수 있는 최대 칸 수

💡 문제 해결 방법
알고리즘: dfs

알고리즘 선택 이유

• 다양한 경로를 깊게 탐색해야 하기 때문에 bfs는 맞지 않다고 판단(예를 들어 아래로 한 칸 내려갔으면 그 내려간 한 칸으로부터 탐색을 해야 하지만 bfs의 특성상 아래로 내려가기 전에 도달할 수 있는 칸부터 먼저 탐색하므로)

예외처리

• 모든 지점에서 출발해야 함
• 끝점이 정해지지 않았으므로 다음 칸으로 나아갈 경우가 없다면 종료
• 각 위치로부터 시작하여 거리를 측정하고 해당 거리를 저장할 배열 필요
• visited 배열은 시작마다 초기화 필요

스터디 내용

• directed graph(자기보다 큰 쪽으로만 이동)
• cycle이 없음
• map + directed + cycle 이 없으면 DAG이므로 소스(in edge)가 없는 곳에서 시작해야 함 --> 위상 정렬 사용
• 상하좌우에서 작은 녀석이 있으면 in edge +1
• topological sort(위상 정렬): 선호수 체계도

💻 코드

import sys
from collections import deque

def bfs(queue, dist):
    max_dist = 0
    while(queue):
        x, y = queue.popleft()
        max_dist = max(max_dist, dist[x][y])
        adj_list = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
        for nx, ny in adj_list:
            if nx >= 0 and nx<n and ny>=0 and ny<n:
                if graph[x][y] < graph[nx][ny]: # 현 위치보다 다음 위치의 대나무 양이 많다면 갈 수 있음
                    inedge[nx][ny] -=1
                    dist[nx][ny] = dist[x][y] + 1
                    if inedge[nx][ny] == 0:
                        queue.append((nx, ny))

    print(max_dist)


n = int(sys.stdin.readline())
graph = [[0 for x in range(n)]for x in range(n)]
inedge = [[0 for x in range(n)]for x in range(n)]
for i in range(n):
    graph[i] = list(map(int, sys.stdin.readline().split()))

# inedge 조사
# 방향성: 적은 양의 대나무 --> 많은 양의 대나무
for x in range(n):
    for y in range(n):
        d = graph[x][y] # 현재 위치의 대나무양
        adj_list = [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]
        for nx, ny in adj_list:
            if nx >=0 and nx<n and ny>=0 and ny<n:
                nd = graph[nx][ny] # 다음 위치의 대나무양
                if d > nd:
                    inedge[x][y] += 1

queue = deque()
dist = [[0 for x in range(n)]for x in range(n)]
for i in range(n):
    for j in range(n):
        if inedge[i][j] == 0:
            queue.append((i, j))
            dist[i][j] = 1
bfs(queue, dist)

💟 추가적으로 알게 된 점

• 백준 ACM Craft 문제에서 위상정렬과 bfs의 메모리 초과 늪에 빠지고 고생해서 탈출해서 그런지 이번 문제는 같은 알고리즘을 해결
• map 그래프에서도 방향성이 존재하는지 반드시 체크해야 함
• 방향성 + map + no cycle --> DAG 이므로 소스가 없는 곳에서 시작한다 --> 위상정렬 이용