🌞Algorithm/πŸ”₯Baekjoon

[Baekjoon] 1937_μš•μ‹¬μŸμ΄ νŒλ‹€

λΏŒμ•Ό._. 2023. 5. 25. 13:11

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 κ°’ μ—…λ°μ΄νŠΈ 및 μ΅œλŒ“κ°’ μ €μž₯

μƒκ°πŸ€”