백준
백준 1937번 : 욕심쟁이 판다
Huiyeong
2021. 3. 18. 02:14
문제
1937번: 욕심쟁이 판다
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서
www.acmicpc.net
구현 방법
그냥 bfs/dfs를 쓰면 시간 초과가 나기 때문에 dp를 써줘야합니다.
예제를 예로 들면 9->11->15 방향으로 탐색을 합니다.
나중에 5->11로 갈때면 11은 15까지밖에 못간다는걸 이미 알고있는데 탐색을 하므로 시간이 낭비됩니다.
그래서 자기가 이미 갔던 곳이라면 살 수 있는 날을 저장을 하고 그 곳을 또 방문하게 된다면 저장되어 있는 값을 가져와 +1을 해주면 자신의 살 수 있는 날을 계산할 수 있습니다.
자신의 가는 모든 곳의 값을 저장해줘야 하기 때문에 깊이 탐색(dfs)를 쓰고 깊이 들어갔다가 더이상 갈 곳이 없다면 되돌아오면서 +1한 값을 저장해주면 됩니다.
또 생각해야 할 점은 9에서는 상을 제외한 모든 부분을 갈 수 있는데 제일 큰 값은 3이므로 만약 이미 자신에게 값이 있다면 원래의 값과 새로 구한 값을 비교하여 더 큰 값을 저장해줍니다.
구현 코드
package BOJ.Gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ1937_욕심쟁이판다 {
static int N, MAX;
static int[][] dp, check, map, deltas= {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
dp = new int[N][N];
check = new int[N][N];
map = new int[N][N];
for(int i=0;i<N;i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 입력완료
MAX = Integer.MIN_VALUE;
for (int i=0;i<N;i++) {
for (int j=0;j<N;j++) {
if (check[i][j]==0) {
check[i][j] = 1;
dfs(i, j);
MAX = Math.max(MAX, dp[i][j]);
}
}
}
System.out.println(MAX);
}
static void dfs(int r, int c) {
for (int d=0;d<4;d++) {
int nr = r+deltas[d][0];
int nc = c+deltas[d][1];
if (isIn(nr, nc) && map[nr][nc]>map[r][c]) { // 범위내에 있고 해당 대나무 수보다 많으면
// 내가 가려는 곳에 이미 방문을 했고 dp가 있다면 현재 dp와 내가 방문하려던 곳의 dp+1 중 더 큰 값을 저장
if (dp[nr][nc]!=0 || check[nr][nc]!=0) dp[r][c] = Math.max(dp[r][c], dp[nr][nc]+1);
else {
check[nr][nc] = 1;
dfs(nr, nc);
dp[r][c] = Math.max(dp[r][c], dp[nr][nc]+1); // 깊이 들어갔다기 다시 되돌아올때 (위와 설명 동일)
}
}
}
if (dp[r][c]==0) dp[r][c] = 1; // dp가 비어있다면 하루는 버틸 수 있으므로 1 넣어줌
return;
}
static boolean isIn(int nr, int nc) {
return nr>=0 && nr<N && nc>=0 && nc<N;
}
}