알고리즘/완전탐색(BFS,DFS)
BOJ - 2644 ) 촌수계산
개발자가될수있을까?
2020. 1. 28. 20:06
https://www.acmicpc.net/problem/2644
2644번: 촌수계산
사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대
www.acmicpc.net
주어진 두 노드간에 촌수를 계산하는 기본적인 BFS문제이다.
나와 연결된 노드는 1촌의 관계를 가지며
주어진 두 노드간의 거리를 구하는 문제였다.
BufferedReader 사용법이 익숙하지 않아서
새로운줄을 받을때에 토크나이저를 계속 새로 만들어주었는데 이부분을 개선해야겠다.
|
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
52
53
54
55
56
57
58
59
60
61
62
63
64
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
class node{
int no;
int depth;
node(int no, int depth){
this.no = no;
this.depth = depth;
}
}
public class Main {
static int map[][] = new int[101][101];
static boolean visit[]= new boolean[101];
public static void main(String[] args) throws Exception {
int ans = 0;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int m = Integer.parseInt(st.nextToken());
while(m >0) {
st = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
map[y][x] = 1;
map[x][y] = 1;
m--;
}
if(start == end) System.out.println(0);
else {
Deque<node> dq = new ArrayDeque<node>();
dq.add(new node(start,0));
visit[start] = true;
while(!dq.isEmpty()) {
node now = dq.poll();
ans = now.depth;
break;
}
for(int index = 0; index < n +1 ; index++) {
visit[index] = true;
}
}
}
if(ans ==0) System.out.println(-1);
else System.out.println(ans);
}
}
}
|
cs |
