백준 1937번 욕심쟁이 판다

2021년 05월 20일!

무려 dfs를 재귀로 구현하는 것을 모르던 시절

---

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

풀이 맞게 잘 생각해놓고 구현 실수해서 한참 고생한 문제...

판다는 점점 더 많이 먹어야한다

최장거리 구하는 문제

그냥 단순히 깊이우선탐색을 하면 시간초과가 나고 dp로 해결해야했다

각 지점에서 갈 수 있는 최대거리를 dp에 기록했다

일반적인 깊이우선탐색과는 조금 다르게 구현..

from sys import stdin
from collections import deque

n = int(stdin.readline())

g = [list(map(int, stdin.readline().rstrip().split())) for i in range(n)]

dp = [[0 for i in range(n)] for j in range(n)]

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

s = deque()

ans = 0
for i in range(n):
  for j in range(n):
    if dp[i][j] == 0:
      s.append((i,j))
      while s:
        now = s[-1]
        count = 0
        maxlen=1
        for k in range(4):
          nx = now[0] + di[k]
          ny = now[1] + dj[k]
          if 0<=nx<n and 0<=ny<n and g[now[0]][now[1]] < g[nx][ny]:
            if dp[nx][ny]==0:
              s.append((nx,ny))
              dp[nx][ny]=0
              count+=1
            else:
              if maxlen<dp[nx][ny]+1:
                maxlen=dp[nx][ny]+1
            
        if count==0:
          dp[s[-1][0]][s[-1][1]]=maxlen
          s.pop()
          if maxlen>ans:
            ans=maxlen

print(ans)

다른 사람들이 한 것도 봤는데 재귀로 많이 했다

신기하다

나는 아직 멀었다