- Date : 2020.11.17(월)
- Time : 20분
- 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.
for _ in range(m):
a, b = map(int,sys.stdin.readline().split())
if a == 1:
f.append(b-1)
res.add(b-1)
friends[a-1][b-1] = 1
friends[b-1][a-1] = 1
: 먼저 상근이와 직접적으로 친구인지 아닌지를 구분한다. 직접적인 친구라면 f에 저장하고 아니라면 res에 저장해둔다.
while f:
num = f.pop()
for i in range(1,n):
if friends[num][i] == 1:
res.add(i)
: 그리고 친구 목록을 검사하면서 너비 우선 탐색인 bfs로 친구 목록이 빌 때까지 검사해준다.