[Python] 백준 24445번(DFS/BFS)

문제

24445번: 알고리즘 수업 - 너비 우선 탐색 2

입력

• 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
• 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

• 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다.
•  i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다.
• 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

문제 풀이

• 24444번과 동일하게 풀이

백준 24444번(DFS/BFS)

    -> 그래프 정렬 코드만 내림차순으로 수정

         i.sort(reverse = True) 

코드

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

n, m, r = map(int,input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
cnt = 1
for _ in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

# 그래프 정렬
for i in graph:
    i.sort(reverse=True)
# 정점의 방문순서 출력
def bfs(v):
    global cnt
    queue = deque()
    queue.append(v)
    visited[v] = True
    result[v] = cnt
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                cnt += 1
                result[i] = cnt
                queue.append(i)
                visited[i] = True

bfs(r)
# result 출력
for i in range(1, n + 1):
    print(result[i])