μ°λ¦¬ λλΌλ κ°μ‘± νΉμ μΉμ²λ€ μ¬μ΄μ κ΄κ³λ₯Ό μ΄μλΌλ λ¨μλ‘ νννλ λ νΉν λ¬Ένλ₯Ό κ°μ§κ³ μλ€. μ΄λ¬ν μ΄μλ λ€μκ³Ό κ°μ λ°©μμΌλ‘ κ³μ°λλ€. κΈ°λ³Έμ μΌλ‘ λΆλͺ¨μ μμ μ¬μ΄λ₯Ό 1μ΄μΌλ‘ μ μνκ³ μ΄λ‘λΆν° μ¬λλ€ κ°μ μ΄μλ₯Ό κ³μ°νλ€. μλ₯Ό λ€λ©΄ λμ μλ²μ§, μλ²μ§μ ν μλ²μ§λ κ°κ° 1μ΄μΌλ‘ λμ ν μλ²μ§λ 2μ΄μ΄ λκ³ , μλ²μ§ νμ λ€κ³Ό ν μλ²μ§λ 1μ΄, λμ μλ²μ§ νμ λ€κ³Όλ 3μ΄μ΄ λλ€.
μ¬λ¬ μ¬λλ€μ λν λΆλͺ¨ μμλ€ κ°μ κ΄κ³κ° μ£Όμ΄μ‘μ λ, μ£Όμ΄μ§ λ μ¬λμ μ΄μλ₯Ό κ³μ°νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ¬λλ€μ 1, 2, 3, β¦, n (1 β€ n β€ 100)μ μ°μλ λ²νΈλ‘ κ°κ° νμλλ€. μ λ ₯ νμΌμ 첫째 μ€μλ μ 체 μ¬λμ μ nμ΄ μ£Όμ΄μ§κ³ , λμ§Έ μ€μλ μ΄μλ₯Ό κ³μ°ν΄μΌ νλ μλ‘ λ€λ₯Έ λ μ¬λμ λ²νΈκ° μ£Όμ΄μ§λ€. κ·Έλ¦¬κ³ μ μ§Έ μ€μλ λΆλͺ¨ μμλ€ κ°μ κ΄κ³μ κ°μ mμ΄ μ£Όμ΄μ§λ€. λ·μ§Έ μ€λΆν°λ λΆλͺ¨ μμκ°μ κ΄κ³λ₯Ό λνλ΄λ λ λ²νΈ x,yκ° κ° μ€μ λμ¨λ€. μ΄λ μμ λμ€λ λ²νΈ xλ λ€μ λμ€λ μ μ yμ λΆλͺ¨ λ²νΈλ₯Ό λνλΈλ€.
κ° μ¬λμ λΆλͺ¨λ μ΅λ ν λͺ λ§ μ£Όμ΄μ§λ€.
μ λ ₯μμ μꡬν λ μ¬λμ μ΄μλ₯Ό λνλ΄λ μ μλ₯Ό μΆλ ₯νλ€. μ΄λ€ κ²½μ°μλ λ μ¬λμ μΉμ² κ΄κ³κ° μ ν μμ΄ μ΄μλ₯Ό κ³μ°ν μ μμ λκ° μλ€. μ΄λμλ -1μ μΆλ ₯ν΄μΌ νλ€.
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
3
9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
-1
μΌλ¨, μ£Όμ΄μ§ μμ μ
λ ₯ 1μ κ·Έλνλ‘ ννν΄ λ³΄μμ λ, λ κ°μ κ·Έλν ννλ‘ λνλΌ μ μλ€.
κ·Έλ°λ° μ¬κΈ°μ λ¬Έμ 쑰건 μ€ μ΄μλ₯Ό κ³μ°ν΄μΌ νλ μλ‘ λ€λ₯Έ λ μ¬λμ λ²νΈκ° κ°κ° λ€λ₯Έ κ·Έλνμ μνλ€λ©΄, μ΄μκ° μ λ μ΄μ΄μ§ μ μλ ꡬ쑰μ΄λ―λ‘ μ΄ κ²½μ°μλ μ΅μ’
μ μΌλ‘ -1μ λ°νν΄μΌ νλ€.
μ΄ λ¬Έμ λ DFSμ BFSλ‘ λ λ€ ν μ μμ§λ§, λλ DFS λ°©μμ νν΄ νμ΄λ³΄κΈ°λ‘ νλ€.
μμ μ
λ ₯ 1μ κ³μ μμλ‘ λ€μ΄λ³΄μμ λ, DFSμ μΆλ° μ§μ μ 7λ² λ
Έλκ° λλ€.
μ΄μ 3λ² λ
Έλλ₯Ό μ°Ύμκ°λ κΈΈμ΄ μ΄λ»κ² λλ μ§ ν λ² μμλ΄μΌκ² λ€.
λ¨Όμ , 7λ² λ Έλμμ κ° μ μλ κ²½μ°λ 2λ² λ Έλλ°μ μλ€.
λ€μμΌλ‘, 2λ² λ
Έλμμ κ° μ μλ κ²½μ°λ
1λ² λ
Έλλ μκ³ , 8λ² λ
Έλλ μκ³ , 9λ² λ
Έλλ μλ€.
κ·Όλ° DFSλ₯Ό μ½λλ‘ κ΅¬νν λλ λ³΄ν΅ μΈλ±μ€κ° μμ μμλλ‘ λ¨Όμ λ°©λ¬Ένλλ‘ λμ΄μκΈ° λλ¬Έμ, 1λ² λ
Έλλ₯Ό λ°©λ¬Ένλ€κ³ κ°μ νμ.
κ·Έλ λ€λ©΄, μ΄μ 1λ² λ
Έλμμ 3λ² λ
Έλλ‘ κ° μ μλ κΈΈμ΄ μ‘΄μ¬νλ€.
λ°λΌμ, 7λ² λ
Έλμμ 2λ² λ
Έλλ‘, 2λ² λ
Έλμμ 1λ² λ
Έλλ‘, 1λ² λ
Έλμμ 3λ² λ
Έλλ‘,
μ΄ 3λ² λ
Έλλ₯Ό κ±°μ³κ°κΈ° λλ¬Έμ μ΅μ’
μ μΌλ‘ 3μ΄ λ°νλκ³ , μ΄λ 3μ΄μ΄λΌλ λ»μ΄μ΄μΌ νλ€.
κ·Έλ°λ° DFSλ μμ§ λλμ§ μμκΈ° λλ¬Έμ, 2λ² λ Έλμμ 8λ² λ Έλλ₯Ό νμνλ κ³Όμ μ κ±°μΉ κ²μ΄λ€. μ΄ λ, 8λ² λ Έλμμλ λ μ΄μ μμ λ Έλκ° μκΈ° λλ¬Έμ -1μ λ°νν κ²μ΄κ³ , 9λ² λ Έλλ λ§μ°¬κ°μ§μΌ κ²μ΄λ€.
import java.io.IOException;
import java.util.Scanner;
public class Main {
int[][] graph; // κ΄κ³λ
boolean[] visited; // λ
Έλ λ°©λ¬Έ μ¬λΆ μ μ₯
int N; // μ 체 μΈμ
public void solve() throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); // μ 체 μΈμ μ
λ ₯
sc.nextLine(); // λ²νΌ λΉμ°κΈ°
// μ΄μλ₯Ό νμΈν μλ‘ λ€λ₯Έ λ μ¬λ μ
λ ₯
String[] Search = sc.nextLine().split(" ");
int p1 = Integer.parseInt(Search[0]);
int p2 = Integer.parseInt(Search[1]);
int M = sc.nextInt(); // κ΄κ³ κ°μ μ
λ ₯
sc.nextLine(); // λ²νΌ λΉμ°κΈ°
// graph, visitied μΈμ€ν΄μ€ μμ±
graph = new int[N + 1][N + 1];
visited = new boolean[N + 1];
// κ΄κ³ μ
λ ₯
for (int i = 0; i < M; i++) {
String[] input = sc.nextLine().split(" ");
int x = Integer.parseInt(input[0]);
int y = Integer.parseInt(input[1]);
graph[x][y] = 1;
graph[y][x] = 1;
}
// p1μμλΆν° dfs μμ
System.out.print(dfs(p1, p2, 0));
sc.close();
}
public int dfs(int now, int dest, int chon) {
if (now == dest) {
return chon; // μ°Ύμ λ μ¬λμ΄ κ°λ€λ©΄ chon λ°ν
}
visited[now] = true; // νμ¬ λ
Έλ λ°©λ¬Έ νκΈ°
int r = -1; // μ΄κΈ°κ° : -1
for (int i = 1; i <= N; i++) {
if (graph[now][i] == 1 && visited[i] == false) {
int subR = dfs(i, dest, chon + 1); // λ€μ λ
Έλ λ°©λ¬Έ
if (subR != -1 && subR >= r) { // μ°Ύμ λͺ©μ μ§κΉμ§μ μ΄μ μ
λ°μ΄νΈ
r = subR;
}
}
}
return r;
}
public static void main(String[] args) throws IOException {
Main main = new Main();
main.solve();
}
}
μΌλ €λΈμΌλ €λΈπ€ͺ