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

24444번: 알고리즘 수업 - 너비 우선 탐색 1

https://www.acmicpc.net/problem/24444

문제 정의

---

입력으로 주어지는 간선 정보로 BFS를 수행하고 각 노드의 방문 순서를 출력한다.

접근 방법

---

BFS 탐색

문제 해설

---

• 각 노드 정보를 이차원 리스트 정보로 받는다.

• 무방향 그래프 이므로 양방향 간선으로 간주하고 양쪽의 정보를 다 입력한다.

• 시작 노드인 R 부터 DFS를 수행한다.

풀이

---

import sys
from collections import deque

input = sys.stdin.readline

N, M, R = map(int, input().split())

graph = [[] for _ in range(N+1)] 
visited = [False] * (N+1)
order = [0] * (N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(1, N+1):
    graph[i] = sorted(graph[i])
    

q = deque()
cnt = 1

# bfs 함수 정의
def bfs(start):
    global cnt
    visited[start] = True
    order[start] = cnt
    # 방문할 노드 큐에 추가
    for i in graph[start]:
        q.append(i)
    
    while q:
        now = q.popleft()
        if not visited[now]:
            visited[now] = True
            cnt += 1
            order[now] = cnt
            for j in graph[now]:
                q.append(j)

bfs(R)

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

정리

---

• BFS의 원래 시간복잡도는 $O(N)$ 이다.

• BFS 함수 구현은 큐 자료구조를 이용하므로 import하는 라이브러리를 꼭 기억하자! → from collections import deque

• deque에서 왼쪽에서 부터 원소를 뽑아야 하므로 그냥 pop이 아니라 popleft()

Uploaded by N2T