너비 우선 탐색(BFS)

1) 동작 방식

→ 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

→ 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

→ 위 과정을 더 이상 수행할 수 없을 때까지 반복한다.

2) 구현

from collections import deque

n, m, v = map(int, input().split())
graph = [[False] * (n+1) for _ in range(n+1)]

for _ in range(m):
    x,y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

visited = [False] * (n+1)

def bfs(v):
    q = deque([v])
    visited[v] = True

    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            if not visited[i] and graph[v][i] == 1:
                q.append(i)
                visited[i] = True

bfs(v)