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

문제

24480번: 알고리즘 수업 - 깊이 우선 탐색 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을 출력한다.

문제 풀이

• 24479번과 동일하게 풀이

백준 24479번 (DFS/BFS)

     -> 그래프 정렬만 오름차순이 아닌 내림차순으로 코드 수정

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m, r = map(int,input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
cnt = 0
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 dfs(v):
    global cnt
    cnt += 1
    visited[v] = True
    result[v] = cnt
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

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