[알고리즘] 백준 5567 파이썬 - 결혼식

 

5567번: 결혼식

문제

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

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

 

문제풀이

from collections import deque
n=int(input())
m=int(input())
graph=[[]*(n+1) for _ in range(n+1)]
visited=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    queue=deque([v])
    visited[v]=1
    while queue:
    	#01
        x=queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i]=visited[x]+1
dfs(1)
res=0
#02
for i in range(2,n+1):
    if visited[i]<4 and visited[i]!=0:
        res+=1
print(res)

전의 과정은 일단 dfs의 풀이와 같으니 해설을 생략하겠다.

 

- #01 : 1을 시작으로 하여 시작 지점과 연결된 관계를 찾아가며 visited[x]+1을 한다.

           즉 이 결과값으로 노드의 시작값과 어느 관계인지 유추가 가능하다.

- #02 : 완성된 visited의 결과를 보고 자기 자신이 아니며, 친구와 친구까지만 

           즉 2와 3의 이면서 0이 아닌 값이면 res에 1을 더해준다.

           res를 출력해준다.