문제
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.
입력
첫째 줄에 대나무 숲의 크기 n(1 ≤ n ≤ 500)이 주어진다. 그리고 둘째 줄부터 n+1번째 줄까지 대나무 숲의 정보가 주어진다. 대나무 숲의 정보는 공백을 사이로 두고 각 지역의 대나무의 양이 정수 값으로 주어진다. 대나무의 양은 1,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에는 판다가 이동할 수 있는 칸의 수의 최댓값을 출력한다.
접근 방법
-
문제를 보니 아주 간단한 해법이 떠오릅니다. n x n 노드의 모든 위치를 시작으로 BFS를 돌려 판다가 갈 수 있는 위치를 세면 될 것 같습니다.
-
그런데 제출을 해보니 메모리 초과가 발생합니다! 왜 그럴까요? 간단한 예시를 들어봅시다.
- n x n 배열을 임의로 생성해 봅시다.
| 1 | 2 | 3 |
| 6 | 5 | 4 |
| 7 | 8 | 9 | - 1 영역에서 갈 수 있는 결과는 9입니다.
- 2 영역에서 갈 수 있는 결과는 8입니다.
- ...
- 9 영역에서 갈 수 있는 결과는 1입니다.
-
1번에서 떠올린 BFS 해법으로는 최악의 경우인 500 x 500 영역이 위와 같이 설정된 때 탐색을 진행하게 되면 메모리초과가 나게 됩니다.
-
때문에 우리는 이미 지나온 결과를 저장해야 합니다. 아이디어는 1번에서 약간 변경해 DFS로 탐색을 진행하며 지나온 영역들에서 갈 수 있는 결과를 메모리에 저장합니다.
-
2번에서 예시를 들었던 영역을 사용해 탐색을 진행한다면 지나온 영역에서 갈 수 있는 결과는 아래와 같을 것입니다.
| 9 | 8 | 7 |
| 4 | 5 | 6 |
| 3 | 2 | 1 |
⚠️주의할 점⚠️
- 지나온 영역을 저장하는 배열은 모두 -1로 초기화 해줘야 합니다. 0으로 되어있을 경우 이미 지나온 영역으로 판단하게 될 수 있습니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class GreedyPanda {
static int[][] board;
static int[][] visit;
static int[] dx = new int[]{-1, 0, 1, 0};
static int[] dy = new int[]{0, 1, 0, -1};
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
int result = 0;
board = new int[n][n];
visit = new int[n][n];
// 1) 방문한 구역을 담은 visit 배열 -1로 초기화
// 이유: 0으로 초기화 되어있을 경우 이미 방문한 곳으로 처리될 수 있기 때문
for (int i = 0; i < n; i++) {
Arrays.fill(visit[i], -1);
}
// board 초기화
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split(" ");
for (int j = 0; j < n; j++) {
board[i][j] = Integer.parseInt(input[j]);
}
}
// 모든 구역을 탐색해서 가장 긴 거리를 이동할 수 있는 경우를 result 에 저장
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int move = getMoveCount(i, j);
result = Math.max(result, move);
}
}
System.out.println(result);
br.close();
}
public static int getMoveCount(int x, int y) {
// 1) 이미 방문한 구역 : 해당 위치로부터 판다가 갈 수 있는 구역의 수를 담고 있을 경우 반환
if (visit[x][y] > -1) {
return visit[x][y];
}
// 2) 방문하지 않은 구역 : 해당 위치로부터 판다가 갈 수 있는 구역을 모두 탐색해 가장 큰 값을 구하여 반환
int maxMove = 0;
for (int i = 0; i < 4; i++) {
int tmpx = x + dx[i];
int tmpy = y + dy[i];
if (0 <= tmpx && tmpx < n && 0 <= tmpy && tmpy < n && board[tmpx][tmpy] > board[x][y]) {
maxMove = Math.max(maxMove, getMoveCount(tmpx, tmpy));
}
}
// 3) 반환 시에 visit[x][y] 에 값을 저장해 재방문시 이미 방문한 구역 코드에서 반환할 수 있게 처리
return visit[x][y] = maxMove + 1;
}
}결과
