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

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

import sys

input = sys.stdin.readline

from collections import deque

# N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다
# 정점 번호는 1번부터 N번, 모든 간선의 가중치는 1

# 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력

n, m, r = map(int,input().split())

graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)

for _ in range(m):
    u, v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in graph:
    i.sort()

def bfs():
    
    queue = deque([r])

    visited[r] = 1

    count = 2

    while queue:
        
        v = queue.popleft()

        for next in graph[v]:
            if visited[next] == 0:
                queue.append(next)
                visited[next] = count
                count += 1

bfs()

for i in range(1,n+1):
    print(visited[i])

 

이번 문제는 BFS 알고리즘을 실행했을 때 1부터 n까지의 정점을 각각 방문한 순서를 출력하는 문제이다.

 

처음에는 다른 유형들처럼 방문한 원소들을 차례대로 출력하는 문제인줄 알았는데, 알고보니 R 정점에서 시작하여 각 정점들을 방문한 순서를 반환하는 문제였다.

 

따라서 visited를 True/False가 아니라 0으로 초기화하고 다른 정점을 방문할 때마다 count + 1 해주어 순서를 매겨주었다.

 

아는 유형의 문제라고해서 문제를 대충 읽고 성급하게 풀지말고, 문제를 유심히 읽는 습관을 들이자.