백준 5567 결혼식

결혼식

문제는 백준에서 확인 할 수 있다.

✔ 접근방법

• 구현
• 그래프 탐색, BFS

BFS로 탐색하고, 뎁스를 고려하여 정답을 구해낸다.

✔ 코드

import sys
from queue import deque

def solution(friends):
    answer = []
    if friends.get(1, None) == None:
        print(0)
        return
    
    queue =  deque([ [i, 1] for i in friends[1] ])
    
    while( queue ):
        q = queue.popleft()
        sid = q[0]
        depth = q[1]

        if depth <= 2 and sid not in answer and sid != 1:
            answer.append(sid)
        else:
            continue

        for elem in friends[sid]:
            # print(elem)
            if elem in answer:
                continue

            queue.append([elem,depth+1])

    print(len(answer))

if __name__ == "__main__":
    n = int(input())
    m = int(input())

    friends = {}
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        if friends.get(a, None) == None :
            friends[a] = [b]
        else:
            friends[a].append(b)

        if friends.get(b, None) == None :
            friends[b] = [a]
        else:
            friends[b].append(a)

    # print(friends)
    solution(friends)

☝ 팁

깊이 우선을 통해서도 답을 구해낼 수 있지만,
일정한 뎁스에 해당하는 노드들을 찾기 위해서는 BFS가 효율적이다.