[백준] 24444 파이썬(python) : 알고리즘 수업 - 너비 우선 탐색 1

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

 

 

 

 

구글에 검색하면 다른 방식의 풀이들이 많아서 24480번 문제랑 비슷하게 풀어봤습니다.

 

 

import sys
from collections import deque #1
n, m, r = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split()) #2
    graph[a].append(b) #3
    graph[b].append(a)
visited = [0] * (n+1) #4 
count = 1
visited[r] = 1

def bfs(v):
    global count
    q = deque()
    q.append(v) #5 
    while q:
        now = q.popleft()
        for i in sorted(graph[now]): #6
            if visited[i] == 0:
                count += 1
                visited[i] = count
                q.append(i)

bfs(r)

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

 

#1 : bfs를 구현하기 위한 deque 추가

#2 : 반복적인 입력을 위한 readline()함수 사용

#3 : 무방향 그래프 입력

#4 : bfs에 빠지면 안되는 방문처리 리스트

#5 : 처음 시작 노드를 deque에 넣고 시작

#6 : 가장 낮은 수부터 순회하니까 오름차순으로 정렬

 

 

이전과 똑같은 문제를 bfs로 구현하는 문제였습니다.