[알고리즘][Python] 백준(BOJ) 5567 결혼식_파이썬

 

5567 결혼식    https://www.acmicpc.net/problem/5567

5567번: 결혼식

 

 

 

 

 

문제 풀기 전 공부할 것 : 구현, 그래프 탐색

 

 

 

 

 

 

 

풀이

<내용>

• 상근이의 친구와, 친구의 친구를 초대하는 것이므로 dfs로 깊이가 2인 것까지 탐색한다.
• 상근이와 동기들의 친구 관계를 friends에 map으로 정리한다.
• dfs 함수를 만들고 깊이가 2까지 friend set에 넣어준다.
• 이미 확인했는지 여부를 위해 check 리스트를 만들고 상근이 친구 관계부터 dfs를 시작한다.

 

 

 

<코드>

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
friends = {}
for _ in range(m):
    a, b = map(int, input().split())
    
    if a in friends:
        friends[a].append(b)
    else:
        friends[a] = [b]
        
    if b in friends:
        friends[b].append(a)
    else:
        friends[b] = [a]
        
def dfs(i, c):
    global friend
    if i != 1:
        friend.add(i)
    if c == 2:
        return
    for j in friends[i]:
        if not check[j]:
            check[j] = True
            dfs(j, c+1)
            check[j] = False
    
    
    
check = [False for _ in range(n+1)]
friend = set()
check[1] = True
if 1 in friends:
    dfs(1, 0)

print(len(friend))