[Java/백준/DFS, DP] 1937번: 욕심쟁이 판다

 

문제 링크

www.acmicpc.net/problem/1937

1937번: 욕심쟁이 판다

 

골드 3 문제다. 읽자마자 실버 수준의 DFS로 풀었다가 슬픈 결과를 여러번 맞이했다.

아래부터

1) DFS만 사용했다가 시간초과 발생

2) DP 사용했는데 max값 잘못 계산

반례 : 

2

2 2

2 2

3) 성공

 

 

 

시간초과 코드

DFS만 이용한 경우이다.

boolean[][] visited를 매개변수로 가지고 이동하면서 선택한 블록에 대한 경로를 저장한다.

dfs에서 cnt는 더 이상 갈 블럭이 없을 때 max값과 비교해서 갱신하기 위해 넣어주었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int max, N;
	static int[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		
		StringTokenizer st = null;
		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++) {
				dfs(i, j, new boolean[N][N], 1);
			}
		}

		System.out.println(max);
		br.close();
	}

	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	private static void dfs(int y, int x, boolean[][] visited, int cnt) {
		
		if(visited[y][x]) {
			max = Math.max(max, cnt);
			return;
		}
		
		visited[y][x] = true;
		
		for (int i=0; i<4; i++) {
			int ty = y + dy[i];
			int tx = x + dx[i];
			
			if(ty<0 || tx<0 || ty>=N || tx>=N || map[y][x] >= map[ty][tx])
				continue;
			
			dfs(ty, tx, visited, cnt+1);
		}
		
		
	}
}

 

 

 

정답 코드

메모이제이션과 DFS를 이용했다.

visited 배열 대신 int[][] day를 사용한다.

 

- 새로이 들어가는 (i, j) 블럭에서 day를 1로 갱신한다.

- tmp는 현재 자신의 블록 1로 초기화한다.

- 사방탐색을 하면서 각 위치를 선택했을 때의 dfs 결과를 tmp에 더한다. ( tmp = 1 + dfs )

- 원래 day와 tmp를 비교해서 더 큰 것이 들어간다.

 

어떤 블록으로 판다가 이동했을 때, 이미 day가 있다면 그것을 사용한다. (메모이제이션)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int max, N;
	static int[][] map, day;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		day = new int[N][N];
		
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			Arrays.fill(day[i], -1);
			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(day[i][j]==-1) dfs(i, j);
			}
		} 

		System.out.println(max);
		br.close();
	}

	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	private static int dfs(int y, int x) {
		
		if(day[y][x] != -1) {
			return day[y][x];
		}
		
		day[y][x] = 1;
		
		for (int i=0; i<4; i++) {
			int ty = y + dy[i];
			int tx = x + dx[i];
			
			if(ty<0 || tx<0 || ty>=N || tx>=N || map[y][x] >= map[ty][tx])
				continue;
			
			int tmp = 1;
			tmp += dfs(ty, tx);
			day[y][x] = Math.max(day[y][x], tmp);
		}
		max = Math.max(max, day[y][x]);
		
		return day[y][x];
		
	}
}