백준 1937 욕심쟁이 판다
문제 설명
- nxn 크기의 대나무 숲이 있다.
- 욕심쟁이 판다는 대나무 숲에서 대나무를 먹는다.
- 판다는 현재 위치에서 대나무를 다 먹은 경우 상, 하, 좌, 우 한 곳으로 이동한다.
이때 현재 위치의 대나무수 보다 많은 수의 대나무가 있는 위치로 이동한다.
- 판다를 어느 위치에도 놓을 수 있다.
- 판다가 최대한 오래 살 수 있는 일수를 구하라.
입력 값
- 첫째 줄에 대나무 숲의 크기 n( 1 <= n <= 500) 이 주어진다.
- 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다.
- 대나무 숲의 정보는 공백 사이러 두고 각 지역의 대나무의 양이 정수 값으로 주어진다.
대나무의 양은 100만 이하의 자연수이다.
예제
문제 분석
- 간단하게 생각하면, 해당 위치에서 팬더가 살 수 있는 모든 경우의 수를 확인한다.
- 해당 방법은 nxn의 대나무 숲에서 모든 방법을 찾는 방법은 모든 경로를 살펴보아야 하기 때문에 $n^2$의 경우의 수가 있다.
- 즉, 시간 복잡도는 O($n^4)가 된다. 즉, $500^4$ = 625억이 되기 때문에 불가능하다.
- 문제를 다시 살펴보면, 해당 위치에서 팬더가 오래 살 수 있는 일수는 정해져 있다.
그렇기 때문에 해당 위치에서 오래 살 수 있는 일 수를 한 번 계산하면, 다시 계산할 필요가 없다는 것이다.
- 즉, 이 문제는 DFS + 메모이제이션을 이용하여 해결할 수 있다.
- 방법을 정리하자면
1. nxn 위치를 모두 살펴보면서 해당 위치에서 dfs를 시작한다.
2. 해당 위치에서 오래 살 수 있는 최대 일수를 구하여 저장한다.
3. 해당 위치를 이미 계산했다면 그 값을 사용하고, 아니면 dfs를 계속 실행한다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
int n;
int dy[]{ 0,0,1,-1 };
int dx[]{ 1,-1,0,0 };
// 해당 위치 대나무 수
int boards[501][501];
// 해당 위치에서 시작했을 때 최다 대나무 개수
int visited[501][501];
int dfs(int y, int x) {
if (visited[y][x] != 0) {
return visited[y][x];
}
int nowCost = boards[y][x];
visited[y][x] = 1;
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 0 || nx < 0 || ny >= n || nx >= n || nowCost >= boards[ny][nx]) {
continue;
}
visited[y][x] = max(visited[y][x], 1 + dfs(ny, nx));
}
return visited[y][x];
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int c;
cin >> c;
boards[i][j] = c;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] != 0) {
continue;
}
result = max(result, dfs(i, j));
}
}
cout << result << endl;
return 0;
}
'알고리즘 > 알고리즘 문제풀이' 카테고리의 다른 글
[BOJ-2098] 외판원 순회 (C++) (0) | 2021.07.08 |
---|---|
[BOJ-1939] 중량제한 (C++) (0) | 2021.07.07 |
[BOJ-1922] 네트워크 연결(C++) (1) | 2021.07.05 |
[BOJ-1613] 역사(C++) (1) | 2021.07.05 |
[BOJ-1162] 도로포장(C++) (0) | 2021.07.04 |
댓글