백준 - 2644 - 촌수계산
2021. 3. 25. 18:34ㆍAlgorithm
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
import java.util.*;
public class 촌수계산 {
private static int start;
private static int end;
private static List<List<Integer>> adList = new ArrayList<>();
private static Set<Integer> isVisit = new HashSet<>();
private static int result = -1;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = Integer.parseInt(sc.nextLine());
String[] inputs = sc.nextLine().split(" ");
start = Integer.parseInt(inputs[0]);
end = Integer.parseInt(inputs[1]);
int n = Integer.parseInt(sc.nextLine());
for(int i=0; i<=a; i++) {
adList.add(new ArrayList<>());
}
for(int i=1; i<=n; i++) {
String[] ads = sc.nextLine().split(" ");
int x = Integer.parseInt(ads[0]);
int y = Integer.parseInt(ads[1]);
adList.get(x).add(y);
adList.get(y).add(x);
}
isVisit.add(start);
dfs(start, 0);
System.out.println(result);
}
private static void dfs(int node, int count) {
if(node == end) {
result = count;
return;
}
for(Integer nextNode : adList.get(node)) {
if(!isVisit.contains(nextNode)) {
isVisit.add(nextNode);
count++;
dfs(nextNode, count);
count--;
isVisit.remove(nextNode);
}
}
}
}
|
cs |
알고리즘
DFS
'Algorithm' 카테고리의 다른 글
| 백준 - 12851 - 숨바꼭질2 (0) | 2021.03.26 |
|---|---|
| 백준 - 1697 - 숨바꼭질 (0) | 2021.03.26 |
| 백준 - 1987 - 알파벳 (0) | 2021.03.25 |
| 백준 - 1759 - 암호 만들기 (0) | 2021.03.23 |
| 백준 - 6603 - 로또 (0) | 2021.03.23 |