[Baekjoon Online Judge] 백준 1937번 욕심쟁이 판다(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1937번 욕심쟁이 판다

(C++, Python)

(글쓴날 : 2020.04.23)

 

---

* Baekjoon Online Judge, 백준 1937번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1937번 욕심쟁이 판다

---

1) 문제

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

1937번: 욕심쟁이 판다

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

판다를 n X n 크기의 대나무 숲의 임의의 위치에 풀어 놓을 때, 판다가 최대한 살 수 있는 일수를 구하는 문제입니다.

판다는 현재 위치의 대나무를 먹어치운 뒤 먹은 대나무보다 더 많은 곳으로 이동하며, 만약 이동할 곳이 없을 경우 판다는 죽게 됩니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

처음 접근할 때, 일반적인 DFS로 완전 탐색하여 현재 위치까지 판다가 올 수 있는 최대 일수를 구하는 방식으로 풀었는데 시간 초과가 발생했습니다.

따라서, 접근 방식을 Top-down 방식의 동적 계획법으로 바꾸었고, 현재 위치에서 판다가 살 수 있는 최대 일수를 구하는 방법으로 접근했습니다.

그 결과, 이전에 구해놨던 값들이 확정되어 변동되지 않는 동적 계획법의 특성을 이용해 탐색할 위치의 값들을 재사용할 수 있게 되어 시간 초과가 발생하지 않게 문제를 해결할 수 있었습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
 
using namespace std;
 
int n;
int bambooForest[501][501];
int memoization[501][501];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
int maxAliveDay = 0;
 
int DFS(int i, int j)
{
    if (memoization[i][j])
        return memoization[i][j];
 
    memoization[i][j] = 1;
    int ii = 0;
    int jj = 0;
    int day = 0;
 
    for (int way = 0; way < 4; way++)
    {
        ii = i + dx[way];
        jj = j + dy[way];
 
        if (ii < 0 || ii > n - 1 || jj < 0 || jj > n - 1)
            continue;
 
        if (bambooForest[i][j] < bambooForest[ii][jj])
        {
            day = DFS(ii, jj) + 1;
            if (memoization[i][j] < day)
                memoization[i][j] = day;
        }
    }
 
    return memoization[i][j];
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> bambooForest[i][j];
 
    int aliveDay = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            aliveDay = DFS(i, j);
 
            if (maxAliveDay < aliveDay)
                maxAliveDay = aliveDay;
        }
    }
 
    cout << maxAliveDay;
 
    return 0;
}

---

* Python 코드

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
 
 
def DFS(i, j):
    if memoization[i][j]:
        return memoization[i][j]
    
    memoization[i][j] = 1
 
    for way in range(4):
        ii = i + dx[way]
        jj = j + dy[way]
 
        if ii < 0 or ii > n - 1 or jj < 0 or jj > n - 1:
            continue
 
        if bambooForest[i][j] < bambooForest[ii][jj]:
            day = DFS(ii, jj) + 1
            
            if memoization[i][j] < day:
                memoization[i][j] = day
    
    return memoization[i][j]
 
 
n = int(input())
bambooForest = [list(map(int, input().split())) for _ in range(n)]
memoization = [[0] * n for _ in range(n)]
dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
maxAliveDay = 0
 
for i in range(n):
    for j in range(n):
        aliveDay = DFS(i, j)
        if maxAliveDay < aliveDay:
            maxAliveDay = aliveDay
 
print(maxAliveDay)

---