πAlgorithm/π₯Baekjoon
[Baekjoon] 1937_μμ¬μμ΄ νλ€
λΏμΌ._.
2023. 5. 25. 13:11
λ¬Έμ (μΆμ²: 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 κ° μ λ°μ΄νΈ λ° μ΅λκ° μ μ₯
μκ°π€