문제:
상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.
상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 상근이의 동기의 수 n(2<=n<=500)이 주어진다. 둘째 줄에는 리스트의 길이 m(1<=m<=10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai,bi가 주어진다. (1<=ai<bi<=n) ai와 bi가 친구라는 뜻이며, bi 와 ai도 친구관계이다.
출력:
첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.
풀이방법:
우선 입력으로 받은 값들을 그래프 형식으로 정리를 하는 작업을 거친다. 이후 BFS 방식을 사용해서 level이 2까지 가는 친구들(친구의 친구)을 찾는다. 항상 시작은 1이므로 queue에 1을 넣고 BFS 탐색을 두번 한다. 그렇게 탐색을 마치고 1을 제거한 뒤에 배열의 길이를 출력하도록 한다.
|
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
|
n=int(input())
m=int(input())
friends=[[]for i in range(n+1)]
for i in range(m):
a,b=map(int,input().split())
friends[a].append(b)
friends[b].append(a)
answers=[]
queue=[1]
count=1
while len(queue):
temp=[]
for i in queue[:]:
for j in friends[i]:
if j in answers or count > 2:
continue
else:
answers.append(j)
temp.append(j)
queue.pop(0)
queue=temp
count+=1
answers.remove(1)
print(len(answers))
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]7576. 토마토 (0) | 2019.10.29 |
|---|---|
| [BOJ]1049. 기타줄 (0) | 2019.10.18 |
| [BOJ]1159. 농구 경기 (1) | 2019.10.16 |
| [BOJ]1016. 제곱ㄴㄴ수 (0) | 2019.10.15 |
| [BOJ]2960. 에라토스테네스의 체 (0) | 2019.10.14 |