[Baekjoon] 1937_욕심쟁이 판다

Gold III

문제(출처: https://www.acmicpc.net/problem/1937)

---

< 욕심쟁이 판다 >

 

문제 풀이

 

처음에 dfs만 활용하여 문제를 해결하려고 했었다. 하지만 시간 초과가 발생했고 dp도 함께 사용해야 한다는 것을 알게 되었다. 이미 dfs 탐색을 통해 값을 구했다면 배열에 저장해 두고 다시 탐색을 하지 않도록 구현하여 시간을 줄이는 방법을 택하였다.

 

 

 

 - my solution (Java)

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

public class Main {
	static int arr[][], dp[][], n, result;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

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

		n = Integer.parseInt(bf.readLine());
		arr = new int[n][n];
		dp = new int[n][n];
		result = 1;

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = 1;
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dfs(i, j);
			}
		}

		System.out.println(result);
	}

	private static int dfs(int i, int j) {
		int max_value = 1;
		for (int k = 0; k < 4; k++) {
			int x = i + dx[k];
			int y = j + dy[k];
			if (x >= 0 && x < n && y >= 0 && y < n && arr[i][j] < arr[x][y]) {

				if (dp[x][y] > 1) {
					if (max_value < 1 + dp[x][y])
						max_value = 1 + dp[x][y];
				}
				else {
					int num = dfs(x, y);
					if (max_value < 1 + num)
						max_value = 1 + num;
				}
			}
		}
		dp[i][j] = max_value;
		if (result < max_value)
			result = max_value;

		return dp[i][j];
	}
}

 

• Main
  • n : 대나무 숲 크기 입력
  • arr: 대나무 숲 정보 입력
  • dp: 이동할 수 있는 칸의 정보 저장
  • arr에 대해서 하나씩 다 dfs 탐색 후 최댓값 출력
• dfs
  
  • 현재 위치에서 상하좌우 탐색
  • 대나무 숲 범위 안이며 전 지역보다 대나무가 많다면 이동
  • 이동한 위치가 이미 탐색된 지역이라 dp에 값이 저장되어 있다면 그 값을 활용하여 max값 구하기/ 탐색한 곳이 아니라면 dfs 탐색 후 max 값 구하기
  • dp 값 업데이트 및 최댓값 저장

---

생각🤔

---