HelloMinchan
처음처럼
HelloMinchan
LinkedIn
전체 방문자
오늘
어제
  • 분류 전체보기 (306)
    • Backend (4)
      • NestJS (1)
      • Express (1)
      • Spring (2)
    • Infrastructure (1)
      • AWS (1)
    • Frontend (1)
      • Next.js (1)
    • Language & Runtime (4)
      • Java (2)
      • Node.js (2)
    • Computer Science (8)
      • Computer Networks (3)
      • Operating Systems (4)
      • OOP (1)
    • 독서 (4)
      • 데이터 중심 애플리케이션 설계 (3)
      • 객체지향의 사실과 오해 (1)
    • 회고 (4)
      • Project (2)
      • Career (2)
    • Deprecated (280)

채널

  • GitHub
  • LinkedIn

최근 글

태그

  • 데이터베이스
  • 개발자
  • 백준C++
  • 백준
  • 백준Go
  • Algospot
  • front-end
  • 백준Python
  • 백엔드
  • 프로그래머스Python
  • 프로그래머스C++
  • 알고스팟
  • 프로그래머스
  • Baekjoon Online Judge
  • 알고스팟Python
  • Database
  • programmers
  • 프로그래밍
  • 코딩
  • back-end

최근 댓글

인기 글

hELLO
HelloMinchan

처음처럼

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

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

2020. 4. 23. 14:14

© 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번: 욕심쟁이 판다

n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이

www.acmicpc.net


2) 풀이 과정

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

 

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

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

 

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

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

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

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


3) 코드

 

* C++ 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)

 

저작자표시 비영리 변경금지 (새창열림)

'Deprecated' 카테고리의 다른 글

[Baekjoon Online Judge] 백준 2631번 줄세우기(C++, Python)  (0) 2020.04.24
[Baekjoon Online Judge] 백준 1915번 가장 큰 정사각형(C++, Python)  (0) 2020.04.24
[GraphQL] GraphQL이란 무엇인가?  (1) 2020.04.23
[Baekjoon Online Judge] 백준 11051번 이항 계수 2(C++, Python)  (0) 2020.04.22
[Baekjoon Online Judge] 백준 9252번 LCS 2(C++, Python)  (0) 2020.04.22
    'Deprecated' 카테고리의 다른 글
    • [Baekjoon Online Judge] 백준 2631번 줄세우기(C++, Python)
    • [Baekjoon Online Judge] 백준 1915번 가장 큰 정사각형(C++, Python)
    • [GraphQL] GraphQL이란 무엇인가?
    • [Baekjoon Online Judge] 백준 11051번 이항 계수 2(C++, Python)
    HelloMinchan
    HelloMinchan
    Though you should not fear failure, You should do your very best to avoid it.

    티스토리툴바