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

문제

24444번: 알고리즘 수업 - 너비 우선 탐색 1 (acmicpc.net)

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

입력

• 첫째 줄에 정점의 수 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을 출력한다.

문제 풀이

• 그래프의 방문 여부를 알 기위한 visited 배열생성
• 방문 순서를 저장할 result배열도 별도로 생성
• 그래프 오름차순으로 정렬
• 큐에 출발하는 노드 값을 넣고, 출발하는 노드 방문처리 및 방문순서 1값 넣기
• 그 후 방문하는 노드들을 차례대로 큐에 넣고, 방문순서 더해서 result 배열에 넣어주기
• result 첫 번째 인덱스부터 차례대로 출력

코드

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()
# 정점의 방문순서 출력
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])