카테고리 없음
[백준] 5567 결혼식
0298
2020. 12. 6. 17:35
5567번: 결혼식
2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다.
www.acmicpc.net
2020-12-06
|
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
|
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main5567 {
public static int N, M, answer;
public static List<List<Integer>> list;
public static Queue<Integer> q;
public static boolean vtd[];
public static void solve() {
int time = 0;
loop:while(!q.isEmpty()) {
int size = q.size();
while(size > 0) {
int x = q.poll();
for(int i : list.get(x)) {
if(!vtd[i]) {
q.add(i);
vtd[i] = true;
answer++;
}
}
size--;
}
time++;
if(time == 2) break loop;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
list = new ArrayList<>();
q = new LinkedList<Integer>();
vtd = new boolean[N+1];
answer = 0;
for(int i = 0; i <= N; i++) list.add(new ArrayList<>());
for(int i = 0; i < M; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
list.get(a).add(b);
list.get(b).add(a);
}
vtd[1] = true;
q.add(1);
solve();
System.out.println(answer);
}
}
|
cs |
#문제풀이
1. 서로 친구인 경우 연결한다.
2. 상근이의 학번인 1을 기준으로 친구들을 체크하면서, 친구의 친구까지만 결혼식에 초대할 수 있으므로 depth가 2일때까지만 체크한다.
#체크포인트
1. 런타임 에러
- 처음 제출하자마자 런타임 에러가 떠서 문제 입력값을 다시 체크해봤다. 동기의 수 n (2 ≤ n ≤ 500)이라는 조건이 있고 상근이의 학번이 1부터 시작하므로 arraylist가 N만큼 들어가야한다.