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

1937번: 욕심쟁이 판다 (acmicpc.net)

1937번: 욕심쟁이 판다

 

 

import sys
from collections import deque
input = sys.stdin.readline

sys.setrecursionlimit(100000)

def dfs(x, y):
    if dp[x][y] != -1:
        return dp[x][y]
    dp[x][y] = 1

    for i, j in dir:
        nx = x + i
        ny = y + j
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            continue
        if arr[x][y] < arr[nx][ny]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny) +1)
    return dp[x][y]

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
dp = [[-1 for _ in range(n)] for _ in range(n)]
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans, dfs(i,j))

print(ans)

---

import sys
from collections import deque
input = sys.stdin.readline

def dfs(x, y):
    node = deque()

    dir = [(1,0), (-1,0), (0,1), (0, -1)]
    node.append((x, y))
    visited.append((x,y))
    cnt = 1
    while node:
        curX, curY = node.pop()

        for i, j in dir:
            nx = curX + i
            ny = curY + j
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if arr[nx][ny] > arr[curX][curY] and (nx, ny) not in visited:
                visited.append((nx,ny))
                node.append((nx,ny))
                cnt += 1
    return cnt

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

ans = 0
for i in range(n):
    for j in range(n):
        if (i,j) not in visited:
            ans = max(ans, dfs(i,j))

print(ans)

시간초과 난 코드임니다

 

질문게시판 보다 알아낸건데

이 문제는 dfs + dp로 풀어야한대요

import sys
from collections import deque
input = sys.stdin.readline

sys.setrecursionlimit(100000)

def dfs(x, y):
    if dp[x][y] != -1:
        return dp[x][y]
    dp[x][y] = 1

    for i, j in dir:
        nx = x + i
        ny = y + j
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            continue
        if arr[x][y] < arr[nx][ny]:
            dp[x][y] = max(dp[x][y], dfs(nx, ny) +1)
    return dp[x][y]

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
dp = [[-1 for _ in range(n)] for _ in range(n)]
dir = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans, dfs(i,j))

print(ans)

 

set머시기 코드 추가한 이유는 아래 오류가 떠서 추가했어요

DFS 완벽 구현하기 [Python] (tistory.com)BFS 완벽 구현하기 - 파이썬 (tistory.com)