[BOJ] 24444 | 알고리즘 수업 - 너비 우선 탐색 1

아래 백준 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

[BOJ] 24479 | 알고리즘 수업 - 깊이 우선 탐색 1과 비슷하다. 하지만 DFS와 BFS는 엄연히 다른 법이지요 ~

📢 참고 : 기억이 안난다면 DFS와 BFS 정리 를 확인해보쟈.

DFS는 재귀를 이용해서 풀었다면 BFS는 큐를 이용해서 풀면 된다.
시작 노드에서 방문 가능한 점들을 큐에 넣고, 큐가 빌 때 까지 계속 돌면서 노드를 방문해주면 된다.

코드

---

import sys
from collections import deque
sys.setrecursionlimit(10**8)

N, M, R = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort()

def BFS(graph, r, visited):
    t = 1

    q = deque([r])

    visited[r] = True
    result[r] = t
    t += 1

    while q:
        v = q.popleft()
        for node in graph[v]:
            if not visited[node]:
                q.append(node)
                visited[node] = True
                result[node] = t
                t += 1

result = [0] * (N+1)
visited = [False] * (N+1)
t = 1

BFS(graph, R, visited)

for i in range(1, N+1):
    print(result[i])

결과

---