[ Baekjoon - 11/16 ] - 1937번: 욕심쟁이 판다

문제 링크 : https://www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

소요 시간 : 2시간 반

욕심쟁이 판다 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	35720	11499	7634	29.710%

문제

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.

이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.

입력

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

출력

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

예제 입력 1 복사

4
14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

예제 출력 1 복사

4

 

1.  문제를 읽고 이해하기

▶ 입출력 형태 및 조건

1 >   n (대나무 숲의 크기, n : [1, 500]) 

2 >   i1 i2 i3 ... in (대나무 숲의 정보 -> 각 칸에 있는 대나무의 수, 대나무의 양 : [1, 100만]) 

3 >   // n-1만큼 2번줄 반복

출력 > 판다가 이동할 수 있는 최대 칸의 수

 

 

▶ 문제

n x n의 대나무 숲에서 판다가 상하좌우 중 하나를 선택하여 이동하며 대나무를 먹음

판다는 다음 이동할 곳을 정할 때, 현재 지역보다 더 많은 대나무가 있는 곳으로 가야함

판다가 가장 많이 이동할 수 있는 횟수를 출력하는 문제

 

 

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

 

2.  문제를 익숙한 용어로 재정의와 추상화

맵에서 상하좌우 움직이는데, 조건이 전보다 대나무가 많은 곳임. 

더 이해가 필요한 사항은 없으므로 생략

 

3.  문제 해결 방안

1st 접근 ) 완탐

맵이고 상하좌우 이동하는 형태이므로 우선 완탐이 가능할지 고민해보았다.

우선 판다는 임의의 곳에서 출발할 수 있으므로 판다 출발지를 고르기 => O(nxn)

완탐의 경우에는 DFS와 BFS를 이용하는데, 

1. BFS의 경우 큐를 이용해 방문할 곳을 저장하므로, 모두 방문할 수 있을 때가 최악조건 즉, O(nxn)

2. DFS의 경우 재귀를 이용해 방문한 곳을 저장하며 나아가므로, O(4^n)

둘다 출발지를 선택하고 완탐을 수행해야 하므로,
BFS는 O(n^4), DFS는 O(nxnx4^n)으로 불가능하다.. 

 

2nd 접근 ) BFS와 DP

BFS를 진행하면서, 큐에 dp값을 같이 넣어 실행하면 시간을 많이 줄일 수 있을 것이라 생각하였다.

반례)

최장거리를 구해야하므로, 방문했던 곳을 또 방문해야할 수 있기 때문에, 메모리초과가 발생할 수 있음!

그리고 위 문제는 n이 최대 500이므로 BFS를 사용하면 너무 많은 데이터를 큐에 넣으므로 불가능.

 

3rd 접근 ) DFS와 DP

DP를 이용해 메모이제이션을 활용하여 중복방문을 최소화시킬 수 있다.

여기서 DP는 해당 좌표에서 출발했을때, 최대로 이동할 수 있는 칸 수이다.

왼쪽 표에 대하여 dp를 구해보면 오른쪽 표와 같이 나오게 된다.

DFS는 방문할 수 있다면 재귀로 깊게 들어가고, 더 나아가지 못할 때 값을 반환하며 돌아오기 때문에 최대로 이동 가능한 칸 수를 저장할 수 있다.

이렇게 DP를 구해두면 중복방문을 할 필요가 없으므로(이미 최댓값을 알고있기 때문에) O(nxn)으로 실행을 끝낼 수 있다!

 

4.  위 계획 검증

위 3번째 접근에서 다뤘으므로 생략

 

5.  코드 작성

▶ Java 11 ( 37680KB, 556ms)

import java.util.*;
import java.io.*;

public class Main {
    static int N, ans;
    static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };
    static int[][] map, dp;

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        // 맵에 값넣기 -> O(N*N)
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 모든 좌표에 대해 DFS -> 메모이제이션으로 인해 이중 for문과 DFS 실행시간 합하여 O(N*N)
        dp = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ans = Math.max(ans, DFS(i, j));
            }
        }

        bw.write(ans + "\n");
        bw.flush();
    }

    public static int DFS(int x, int y) {
        if (dp[x][y] != 0) {
            return dp[x][y];
        }
        dp[x][y] = 1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0<=nx && nx<N && 0<=ny && ny<N && map[x][y] < map[nx][ny]) {
                dp[x][y] = Math.max(dp[x][y], DFS(nx, ny) + 1);
            }
        }
        return dp[x][y];
    }
}

 

▶ Python 3 ( 51620KB, 772ms)

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

def solution():
    n = int(input())
    board = [list(map(int, input().rstrip().split())) for _ in range(n)]
    # dp = 각 좌표에서의 최대로 갈수있는 칸 수
    dp = [[0] * n for _ in range(n)]
    dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def dfs(x: int, y: int) -> int:
        if dp[x][y] != 0:
            return dp[x][y]
        dp[x][y] = 1
        for dx, dy in dxy:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < n and 0 <= ny < n and board[x][y] < board[nx][ny]:
                dp[x][y] = max(dp[x][y], dfs(nx, ny) + 1)
        return dp[x][y]

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

if __name__ == '__main__':
    solution()

 

6.  결과

초반의 시간초과 1개와 틀렸습니다 2개는 BFS를 시도하려다 얻은 결과이다.

맞았습니다 뒤에 얻은 시간초과는... 좀더 시간을 줄여보고자, 함수로 넘어갔다가 바로 리턴되어 돌아오는 것보다는 삼항연산자로 바로 거를 수 있다면 깔끔할 것 같아 해본 시도였지만, 오히려 시간초과를 얻어 당황스러웠던 부분이다..

왼쪽이 시간초과, 오른쪽이 맞았습니다를 얻은 코드이다. 아직도.. 이해가 안된다ㅠ

런타임에러는 파이썬의 RecursionError는 파이썬의 기본 재귀함수 깊이인 1000을 초과했을 때 발생하는 오류여서 임의로 한도를 늘려 맞았습니다를 얻었다.