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

문제

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

 

풀이

그래프 탐색 이용

1. 정점 번호 오름차순 정렬

2. BFS를 이용한 풀이

3. 정점 방문 전 숫자 1 증가

 

예시

5 5 1
1 4
1 2
2 3
2 4
3 4

 

 

코드

import sys
from collections import deque

n, m, r = map(int, sys.stdin.readline().rstrip().split())
edges = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    edges[x].append(y)
    edges[y].append(x)

for edge in edges:
    edge.sort()

index = 1
queue = deque([r])
visited[r] = index

while queue:
    x = queue.popleft()

    for v in edges[x]:
        if not visited[v]:
            index += 1
            visited[v] = index
            queue.append(v)

print(*visited[1:], sep="\n")