[백준 1937 - JAVA] 욕심쟁이판다

1937번: 욕심쟁이 판다

 

현재 장소보다 대나무가 많은 지역으로만 이동할 수 있는 판다가 가장 오래 살아남는 기간을 구하는 문제!

단순하게 dfs로 풀었다가 시간초과를 받았다.

DP라고해서 고민을 하다가 결국 블로그를 참조했다.

기간을 정해서 DP문제를 집중적으로 푸는 시간을 가져야 할 것 같다... ŏ̥̥̥̥םŏ̥̥̥̥

풀이 방법

dfs를 통해 끝에 도달했을 때 그곳의 cnt(살아남은 날짜)는 1이 된다.
* 더 이상 이동하지 못하기 때문에 그곳에서는 하루만 살 수 있다.

그리고 돌아오면서 이동했던 곳의 cnt를 확인하고 더 클 경우 cnt를 갱신한다.

* 나는 누적되는 방식으로 생각했다! 

1. 판다가 살아남는 횟수를 저장하는 맵 크기의 2차원 배열(v)을 생성한다

2.  모든 좌표를 순회하며 v가 0인 좌표에서 dfs를 수행한다.

   1. cnt를 0으로 초기화 한다.
   2. 상하좌우를 이동하며 대나무가 많은 지역으로 이동한다.
   3. v가 0인 좌표를 만나면 dfs를 수행한다.
   4. 이동했던 곳의 v(이동했던 곳의 cnt)를 비교하여 현재 장소의 cnt를 갱신한다.
   5. 함수를 빠져나올 때 ans는 cnt의 max값으로 계속 갱신한다.

import java.io.*;
import java.util.*;

public class Main {
	public static int N, ans;
	public static int[][] map;
	public static int[][] v;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		v = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (v[i][j] == 0) dfs(i, j);
			}
		}
		System.out.println(ans);
	}
	
	public static void dfs(int x, int y) {
		int cnt = 0;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (map[nx][ny] > map[x][y]) {
				if(v[nx][ny] == 0) dfs(nx, ny);
				
				if(cnt < v[nx][ny]) cnt = v[nx][ny];
			}
		}
		v[x][y] = cnt+1;
		ans = Math.max(ans, v[x][y]);
	}
}