[백준] 24445번 : 너비우선 탐색 - 파이썬 풀이

문제

 

코드

from collections import deque
import sys
input = sys.stdin.readline

n, m, r = map(int, input().split()) # n : 정점 m : 간선의 수 r :시작 정점
graph = [[] for _ in range(n+1)]    # 빈 그래프 2차원 배열 생성
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)				# 연결된 정점들 입력하기
    graph[b].append(a)
    
visited = [0] * (n+1)				# 정점 n이 몇 번째에 방문하는지 
count = 1							# 방문하는 차례
visited[r] = 1						# 시작 정점 r이 첫 번째 순서

queue = deque([r])
while queue:
    q = queue.popleft()
    for i in sorted(graph[q], reverse=True):
        if visited[i] == 0:
            count += 1
            visited[i] = count
            queue.append(i)
for k in range(1, n+1):
    print(visited[k])

 

나의 풀이

✔ visited 변수와 count 변수를 통해 정점 n이 몇 번째에 방문하는지를 표현할 수 있습니다.

visited 배열은 0으로 초기화하여 방문할 때마다 visited[n] = count를 통해 몇 번째에 방문하는지 표시합니다. 

방문하지 않은 정점은 초기값 그대로 0 값을 가지게 됩니다.

 

✔ 인접 정점은 내림차순으로 방문하기에 방문하는 graph[n]을 역순으로 정렬한 후 방문처리 합니다.

간단하게 for 문에서 sorted(graph[q], reverse=True)를 이용하면 sorted() 정렬된 리스트를 반환하므로 내림차순으로 방문하게 됩니다.