[파이썬] 백준 1937: 욕심쟁이 판다 (골드3)

[파이썬] 백준 1937: 욕심쟁이 판다 (골드3)

1937번: 욕심쟁이 판다

---

문제

---

풀이

0. 방향성 생각

• DFS 사용

1. 입력

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

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

 

2. 함수 정의

step = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(x,y):
    
    if visit[y][x] != -1:
        return visit[y][x]
    
    visit[y][x] = 0
    for dx,dy in step:
        nx = x + dx
        ny = y + dy
        
        if 0<=nx<n and 0<=ny<n and arr[y][x] < arr[ny][nx]:
            visit[y][x] = max(visit[y][x],dfs(nx,ny))       
            
    visit[y][x] += 1
    return visit[y][x]

• 첫 방문이면 계속 재귀통해서 DFS 실행 못시킬때까지 들어감.
• 첫 방문에서는 if문을 통과못하고 visit = 1
• 그 상위노드에서는 다른 여러 자식노드를 통해 구한 visit값들 중 최대값 visit[y][x]가 기록되어있는데 이 값과 dfs(nx,ny)를 비교해서 큰 값을 선택함.

3. 출력

for i in range(n):
    for j in range(n):
        if visit[i][j] == -1:
            dfs(j,i)
print(max(map(max,visit)))

 

• 탐색이 아직 안된 곳에서 DFS 실행

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().rstrip()

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

step = [(1,0),(0,1),(-1,0),(0,-1)]
def dfs(x,y):
    
    if visit[y][x] != -1:
        return visit[y][x]
    
    visit[y][x] = 0
    for dx,dy in step:
        nx = x + dx
        ny = y + dy
        
        if 0<=nx<n and 0<=ny<n and arr[y][x] < arr[ny][nx]:
            visit[y][x] = max(visit[y][x],dfs(nx,ny))       
            
    visit[y][x] += 1
    return visit[y][x]

for i in range(n):
    for j in range(n):
        if visit[i][j] == -1:
            dfs(j,i)

print(max(map(max,visit)))

 

코멘트

DFS 너무 헷갈림