/* 1601 욕심쟁이 판다 엔엔의 크기의 대나무 숲이 있습니다. 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 단식 투쟁을 하다가 죽게 됩니다. 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있습니다. 아무 곳에 떨어트려 놓고, 동 서 남 북 방향으로 dfs 를 돌리면 되겠습니다. 그리고 갈 곳이 없을때의 최대 거리를 비교해서 적어두면 됩니다. */ #include <iostream> #include <algorithm> using namespace std; #define SIZE 501 // 501 int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int d[SIZE][SIZE]; int n; int maxVal; int x, y; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; void problemIn() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; } } } void dfs(int depth, int preX, int preY) { maxVal = max(maxVal, depth); for (int i = 0; i < 4; i++) { int nx = preX + dx[i]; int ny = preY + dy[i]; if (nx >= 0 && ny >= 0 && nx < n && ny < n) { if (visit[nx][ny] == 0 && map[nx][ny] > map[preX][preY] && d[nx][ny] < d[preX][preY] + 1) { d[nx][ny] = d[preX][preY] + 1; visit[nx][ny] = 1; dfs(depth + 1, nx, ny); visit[nx][ny] = 0; } } } } void solve() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (d[i][j] == 0) { d[i][j] = 1; visit[i][j] = 1; dfs(1, i, j); visit[i][j] = 0; } } } } int main() { problemIn(); solve(); cout << maxVal << endl; return 0; } |
d 배열을 만드는데, 이것은 가지치기로 시간초과를 예방합니다. 이 배열에 들어가는 것은 옮기기 전과 옮기기 후를 비교해서 옮길 때가 옮기기 전보다 값이 커야만 옮기도록 합니다. 큰 값이 아닌 작은값으로 다시 저장된다면, 최대값을 찾는대 도움이 되지 않습니다. 처음 들어갈때 모두 1로 저장을 하고 시작합니다. 그리고 움직일 때의 조건에, 옆으로 이동하려고 하는데, 이것이 그전의 생존 값보다 커야만 이동을 합니다. 작으면 그 자리에 갔을 때 또 dfs 반복과 동일하기 때문입니다. |