1. 문제
1937번: 욕심쟁이 판다
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에
www.acmicpc.net
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다.
이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무 숲이 주어져 있을 때, 이 판다가 최대한 많은 칸을 이동하려면 어떤 경로를 통하여 움직여야 하는지 구하여라.
2. 풀이
정적 변수
int N | 숲 크기 |
int[][] info | 대다무 숲 정보 |
int[][] dp | dp[i][j]에서 출발했을 때의 최대 이동 횟수 저장 |
int[][] deltas | 사방탐색 이동값 |
Main
info에 숲 정보를 모두 저장한다.
dp 배열을 생성한 후 하나씩 탐색한다.
dp[i][j]에 dfs(i,j)를 저장하고, MAX와 dp[i][j]와 비교해서 더 큰 값을 MAX에 저장한다.
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
info = new int[N][N];
StringTokenizer st;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
for(int j=0;j<N;j++){
info[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[N][N];
int MAX = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dp[i][j] = dfs(i,j);
MAX = Math.max(MAX, dp[i][j]);
}
}
System.out.println(MAX);
}
DFS
이미 dp[i][j]에 저장된 값이 있다면 return dp[i][j]한다.
max는 dp[i][j]이후의 경로 길이다. 현재위치 [i][j]에서 사방탐색하면서 갈 수 있는 위치라면 dfs(ni,nj)를 호출한다.
dfs(ni,nj)와 max값을 비교해서 더 큰 값을 max에 저장한다.
마지막으로 dp[i][j]에 1 + max를 저장하고 그대로 반환한다. 1을 더하는 이유는 현재위치의 경로횟수를 포함하기 위해서다.
private static int dfs(int i, int j){
if(dp[i][j]!=0) return dp[i][j];
int ni,nj, max = 0;
for(int[] d:deltas){
ni = i+d[0];
nj = j+d[1];
if(ni<0||nj<0||ni>=N||nj>=N||info[ni][nj]<=info[i][j]) continue;
max = Math.max(max,dfs(ni,nj));
}
return dp[i][j] = 1 + max;
}
전체 코드
import java.io.*;
import java.util.*;
public class BOJ_1937_욕심쟁이판다 {
static int[][] info, dp;
static int N;
static int[][] deltas = {{1,0},{0,1},{0,-1},{-1,0}};
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(in.readLine());
info = new int[N][N];
StringTokenizer st;
for(int i=0;i<N;i++){
st = new StringTokenizer(in.readLine());
for(int j=0;j<N;j++){
info[i][j] = Integer.parseInt(st.nextToken());
}
}
dp = new int[N][N];
int MAX = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dp[i][j] = dfs(i,j);
MAX = Math.max(MAX, dp[i][j]);
}
}
System.out.println(MAX);
}
private static int dfs(int i, int j){
if(dp[i][j]!=0) return dp[i][j];
int ni,nj, max = 0;
for(int[] d:deltas){
ni = i+d[0];
nj = j+d[1];
if(ni<0||nj<0||ni>=N||nj>=N||info[ni][nj]<=info[i][j]) continue;
max = Math.max(max,dfs(ni,nj));
}
return dp[i][j] = 1 + max;
}
}
3. 결과
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 9625 BABBA - JAVA (0) | 2023.06.29 |
---|---|
[BOJ] 1202 보석 도둑 - JAVA (0) | 2023.06.28 |
[BOJ] 11049 행렬 곱셈 순서 - JAVA (0) | 2023.06.26 |
[BOJ] 18428 감시 피하기 - JAVA (0) | 2023.06.25 |
[BOJ] 10942 팰린드롬? - JAVA (0) | 2023.06.24 |
댓글