[백준] 5567. 결혼식 python

🐳 링크

백준 결혼식

🐕 문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

🐾 풀이 방법

상근이와 친구인 친구들을 f에 저장해놓고, f와 친구인 사람만 확인한 뒤 중복되지 않도록 set에 저장한다.

소스코드

import sys
sys.stdin = open("input.txt","rt")

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
friends = [[0]*n for _ in range(n)]

res = set()
f = list()
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
while f:
    num = f.pop()
    for i in range(1,n):
        if friends[num][i] == 1:
            res.add(i)

print(len(res))