[백준 1937번] 파이썬 - 욕심쟁이 판다

백준 1937 - 욕심쟁이 판다

시간 제한 2초, 메모리 제한 256MB

# 조건

• n × n의 크기의 대나무 숲이 있다.
• 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다.
• 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다.
• 그리고 또 그곳에서 대나무를 먹는다.
• 그런데 단 조건이 있다.
  • 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
• 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다.
• 우리의 임무는 이 사육사를 도와주는 것이다.
• n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

• 첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다.
• 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다.
• 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다.
• 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.

출력

• 첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.

# 접근 방법

시간초과

• 판다가 최대한 많은 칸을 이동하는 것이 핵심이다.
• 모든 곳에서 출발시켜보는 브루트 포스는 시간초과가 발생하게 된다.
• 따라서, 처음 입력받은 대나무의 정보를 (대나무의 수, x좌표, y좌표) 로 리스트에 넣어준 후 대나무의 수가 많은 순서대로 정렬해준다.
• 이 리스트를 순회하며 bfs를 돌려주며 visited 배열에 기록해준다.
• 시작을 1로 하며 현재 칸보다 작은 대나무를 반복할 때는 +1을 해준다.
• 이후 visited 배열에 값이 없다면 bfs 함수를 실행, 아니라면 continue 해준다.
• 마지막에 최댓값을 뽑아주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs(val, i, j):  
    q = deque()  
    q.append((val, i, j))  
    while q:  
        n_val, si, sj = q.popleft()  
        for d in range(4):  
            ni, nj = si+di[d], sj+dj[d]  
            if 0<=ni<N and 0<=nj<N and forest[ni][nj] < n_val:  
                if visited[ni][nj] < visited[si][sj] + 1:  
                    visited[ni][nj] = visited[si][sj] + 1  
                    q.append((forest[ni][nj], ni, nj))  

N = int(input())  
forest = [[*map(int, input().split())] for _ in range(N)]  
info = []  
for i in range(N):  
    for j in range(N):  
        info.append((forest[i][j], i, j))  

info.sort(key=lambda x:x[0], reverse=True)  
visited = [[0] * N for _ in range(N)]  
di, dj = [0, 0, -1, 1], [-1, 1, 0, 0]  
for val, i, j in info:  
    if visited[i][j] == 0:  
        visited[i][j] = 1  
        bfs(val, i, j)  

result = 0  
for i in visited:  
    if result < max(i):  
        result = max(i)  
print(result)

• bfs를 활용하 최대 경로를 찾기 위해 경로를 중복 방문하는 경우가 발생해서 TLE를 받는다.
• 이걸 해결하기 위한 아이디어는 dp를 활용하여 풀어준다.
• 대나무의 개수를 기준으로 모든 좌표를 내림차순 해준다.
• 현재 좌표에서 상하좌우에 더 많은 대나무를 가진 곳이 있다면 temp에 dp 값을 저장해준다.
• temp 값이 존재한다면 temp에서 최댓값 + 1을 현재 dp 좌표에 저장해준다.
  • 내림차순 정렬을 했기에 대나무가 더 많은 곳에서 갈 수 있는 곳의 칸 수를 갱신해나가기 때문에
  • 최대 경로를 구할 수 있다

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
forest = [[*map(int, input().split())] for _ in range(N)]  
info = []  
for i in range(N):  
    for j in range(N):  
        info.append((forest[i][j], i, j))  

info.sort(key=lambda x:x[0], reverse=True)  
dp = [[1] * N for _ in range(N)]  
di, dj = [0, 0, -1, 1], [-1, 1, 0, 0]  
result = 0  
for val, i, j in info:  
     temp = []  
     for d in range(4):  
         ni, nj = i + di[d], j + dj[d]  

         if 0<=ni<N and 0<=nj<N and forest[i][j] < forest[ni][nj]:  
             temp.append(dp[ni][nj])  

     if len(temp) > 0:  
         dp[i][j] = max(temp) + 1  

     if result < dp[i][j]:  
         result = dp[i][j]  

print(result)