[BOJ] 1937 - 욕심쟁이 판다

김우경·2020년 12월 19일

알고리즘

목록 보기

27/69

문제링크

문제 설명

N*N크기의 대나무 숲 각 칸에 대나무가 있다. 팬더가 해당 칸의 대나무를 다 먹으면 상하좌우로 이동하는데, 현재 칸의 대나무보다 더 많은 대나무를 가진 칸으로만 이동이 가능하다. 팬더를 대나무숲 어디에 놓아야 최대한 많은 칸을 이동할 수 있을까?

문제 풀이

시도 1 bfs

bfs를 이용해서 각 칸에서 시작하는 경우의 이동거리를 구하려고 했다.

import sys
from collections import deque

input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N = int(input())
Map = []
for _ in range(N):
    Map.append(list(map(int, input().split())))

def in_bound(x, y):
    if x in range(0, N) and y in range(0, N):
        return True
    else:
        return False

def bfs(x,y):
    queue = deque([[x,y]])
    visited = [[0]*N for _ in range(N)]
    visited[x][y] = 1
    ans = 1

    while queue:
        x,y = queue.popleft()
        #4방향에 대해서
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_bound(nx, ny):    #범위 안이면
                if visited[nx][ny] == 0 and Map[nx][ny] > Map[x][y]: #방문하지 않고 이전 지역보다 대나무가 더 많을때
                    queue.append([nx,ny])
                    visited[nx][ny] = visited[x][y] + 1 #거리
                    ans = max(ans, visited[nx][ny])
    return ans

answer = 1
for i in range(N):
    for j in range(N):
        answer = max(answer, bfs(i,j))
print(answer)

코드는 쉽게 작성했는데 시간초과가 났다^_ㅠ..

시도 2 dp

모르겠어서 구글링해보니까 dp를 이용한 dfs로 풀어야 한다고 한다,, dp는 아직 안익숙해서 이해하는데 한참 걸렸다 ^_ㅠ,,,,,

visited : 각 지점에서 해당 지점을 포함하여 앞으로 며칠을 더 살 수 있는지 저장하는 리스트
DFS를 통해 한 경로를 선택할 때
- 이미 탐색했으면 visited 값을
- 아니면 현재까지 계산한 최대 살 수 있는 날과 dfs를 통해 동서남북 이동할 좌표부터 계산한 값+1을 비교

여기서 이미 탐색한 좌표에 대해 visited값을 그대로 받아올 수 있는 이유는,
얍문님의 블로그를 참고해서 이해했다.

와 같은 경우에 이해하기 쉽게 path가 짧은 (1,3)부터 탐색을 시작하면
(1,3)->(1,2)->(1,1)로 총 3일동안 살 수 있다.
아래 코드의 재귀문에서 알 수 있듯이 좌표마다 차례대로 재귀가 호출되어 visited 배열의 값이
visited[1][1] = 1
visited[1][2] = 2
visited[1][3] = 3 으로 설정된다.

이후에 (0,3)과 같은 지점을 방문했을때는 상하좌우로 검사했을때 방문 가능한 지점 (1,3)으로 움직였을때 (1,3)은 이미 3이라는 값을 계산해서 저장해두었기때문에 한번 더 재귀를 해봤자 같은 값이 나온다. 따라서 이미 값이 저장된 좌표에 대해서는 더 방문할 필요 없음!!

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def in_bound(x, y):
    if x in range(0, N) and y in range(0, N):
        return True
    else:
        return False

def dfs(x, y):
    #이미 계산한 좌표면 더 계산할 필요 없이 바로 리턴
    if visited[x][y]:
        return visited[x][y]
    #방문하지 않은 좌표의 기본값은 1
    visited[x][y] = 1

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_bound(nx, ny):
            if Map[nx][ny] > Map[x][y]:
                #현재까지 계산한 최대 살 수 있는 날과 해당 좌표부터 계산한 값+현재 좌표값 비교
                visited[x][y] = max(visited[x][y], dfs(nx, ny)+1)
    return visited[x][y]
    
N = int(input())
Map = [list(map(int, input().split())) for _ in range(N)]
#각 지점을 포함하여 앞으로 며칠 더 살 수 있는지 계산
visited = [[0]*N for _ in range(N)]
answer = 0
for i in range(N):
    for j in range(N):
        answer = max(answer, dfs(i,j))
print(answer)