[백준] 5567번 결혼식

💡문제접근

• BFS알고리즘으로 접근했다. 방문횟수 배열을 만들어서 상근이의 친구와 상근이의 친구의 친구까지 올 수 있도록 코드를 작성했다.
• 다른 그래프 탐색 문제에 비하면 정말 쉬웠던 문제였다.

💡코드(메모리 : 34132KB, 시간 : 64ms)

from collections import deque
import sys
input = sys.stdin.readline

n = int(input().strip())
m = int(input().strip())
relationship = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().strip().split())
    relationship[a].append(b)
    relationship[b].append(a)


def BFS(graph, start):
    queue = deque()
    queue.append(start)
    visited[start] = 1
    while queue:
        start = queue.popleft()
        for i in graph[start]:
            if not visited[i]:
                visited[i] = visited[start] + 1
                queue.append(i)
    return visited


visited = [0] * (n + 1)
BFS(relationship, 1)
friend = 0
li = BFS(relationship, 1) 
# visited 배열 값 설명
# 상근이 본인 : 1
# 상근이의 친구 : 2
# 상근이의 친구의 친구 : 3
for i in li:
	# 위의 배열 값 설명을 토대로 상근이의 친구의 친구까지 초대 가능하므로 아래와 같은 조건문 작성
    if i < 4 and i > 0:
        friend += 1
# 상근이 본인은 빼줘야하므로 -1 처리 
print(friend - 1)

💡소요시간 : 12m