https://www.acmicpc.net/problem/5567
5567번: 결혼식
문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m
www.acmicpc.net
먼저 친구관계를 인접 리스트로 구현해주고 입력받은 값이 상근이의 친구(1번과 친구)인 경우 바로 큐에 넣어주고 체크한다. 그럼 처음 큐의 사이즈는 상근이의 친구들 수만큼이 되므로 ans 변수(초대할 친구 수)에 큐 사이즈를 저장한다
그리고 상근이의 친구들에 대해서 친구를 조사해준다. 아직 check가 되지 않았다면 ans값\을 증가시킨다. 친구의 친구만 더해주면 되므로 친구의 친구는 큐에 새로 넣지 않는다.
|
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
|
#include<iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> list[501];
bool check[501];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
queue<int> q;
cin >> n >> m;
int x, y;
for (int i = 0; i<m; i++) {
cin >> x >> y;
list[x].push_back(y);
list[y].push_back(x);
//상근이의 친구를 큐에 넣는다.
if (x == 1) {
q.push(y);
check[y] = true;
}
else if (y == 1) {
q.push(x);
check[x] = true;
}
}
//현재 큐 사이즈가 상근이의 친구 수
int ans = q.size();
check[1] = true;
int size;
while (!q.empty()) {
x = q.front();
q.pop();
size = list[x].size();
for (int k = 0; k < size; k++) {
y = list[x][k];
if (check[y]) continue;
ans++;
check[y] = true;
}
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 1654. 랜선 자르기 (0) | 2020.01.20 |
|---|---|
| [BOJ] 10816. 숫자 카드 2 (0) | 2020.01.20 |
| [BOJ] 7662. 이중 우선순위 큐 (0) | 2019.11.13 |
| [BOJ] 17472. 다리 만들기 2 (0) | 2019.10.16 |
| [BOJ] 2146. 다리 만들기 (0) | 2019.10.16 |