https://www.acmicpc.net/problem/1937
그냥 평범하게 DFS, BFS로 풀다간 시간 초과가 납니다.
메모이제이션을 통해 해당 좌표마다 최대로 살 수 있는 날을 계산하여 넣어두고,
해당 좌표를 가게되면 연산이 아닌 바로 그 값을 더할 수 있게 해줘야 합니다.
예를들어 예제에서 (0,1)에서 최대 살 날은 3이므로 3으로 저장해 두고, 다른 곳에서 팬더를 출발시키다가
(0,1)로 가게되면 더 이상 계산하지말고 살 날을 바로 더해서 계산을 끝내야 합니다.
#include <iostream>
using namespace std;
int n, result;
int map[501][501];
int life[501][501];//대나무 루트 중 제일 오래살 수 있는 날
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int dfs(int x, int y) {
if (life[x][y]) return life[x][y];
life[x][y] = 1;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n&&ny < n
&&map[x][y] < map[nx][ny]) {
life[x][y] = life[x][y] > dfs(nx, ny) + 1 ?
life[x][y] : dfs(nx, ny) + 1;
}
}
return life[x][y];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (life[i][j] == false)
result = result >= dfs(i, j) ? result : dfs(i, j);
}
}
cout << result;
}
2nd
#include <iostream>
using namespace std;
int n, map[501][501];
bool ch[501][501];
int len[501][501];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
int max(int a, int b) {
return a > b ? a : b;
}
int dfs(int sx, int sy) {
if (len[sx][sy])return len[sx][sy] + 1;
for (int i = 0; i < 4; i++) {
int nx = sx + dx[i];
int ny = sy + dy[i];
if (nx >= 0 && ny >= 0 && nx < n&&ny < n && !ch[nx][ny]
&& map[sx][sy] < map[nx][ny]) {
ch[nx][ny] = true;
len[sx][sy] = max(dfs(nx, ny), len[sx][sy]);
ch[nx][ny] = false;
}
if (i == 3 && len[sx][sy] == 0) len[sx][sy] = 1;
}
return len[sx][sy] + 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
int result = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!len[i][j]) result = max(result, dfs(i, j) - 1);
}
}
cout << result;
}
- 나 혼자 말하고 나 혼자 듣는 말
머리 깨지는 줄….
이런 방식은 처음 풀어봐서 너무 힘들었다..
근데 유익한 시간이었다. 메모이제이션과 DFS의 조합이라니 허허..