백준 24444번: 알고리즘 수업 - 너비 우선 탐색 1 [python]

난이도 : 실버 2
유형 : 너비우선탐색 - BFS
https://www.acmicpc.net/problem/24444

문제 접근

너비 우선 탐색 BFS를 구현하는 문제이다.
BFS에 관한 내용은 BFS에 정리해보았지만 다른 좋은 글들이 많으니 그것들을 참고하길 바란다.

BFS, 너비우선탐색의 절차는 다음과 같다.

1. 입력값 정의
2. 그래프 초기화
3. 인접 노드 방문 순서 정렬
4. 방문 여부 리스트 생성
5. BFS 함수 정의 (큐 기반)
6. BFS 시작

등의 절차로 구현해보겠다.

내 해답 및 풀이

import sys
from collections import deque

input = sys.stdin.readline


# 1. 입력값 정의
N, M, R = map(int,input().split())
edges = []
for _ in range(M):
    u, v = map(int,input().split())
    edges.append((u, v))

# 2. 그래프 초기화
graph = []
for i in range(N + 1):
    graph.append([])

for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

# 3. 인접 노드 방문 순서 정렬 , (오름차순)
for i in range (1, N+1):
    graph[i].sort()

# 4. 방문 여부 리스트 생성
visited = [False] * (N + 1)

order = [0] * (N + 1)
cnt = 1
# 5. BFS 함수 정의 (큐 기반)
def BFS(start):
    global cnt
    queue = deque([start])  # 시작 정점을 큐에 넣음
    visited[start] = True   # 시작 정점을 방문 처리
    order[start] = cnt      # 시작 정점의 방문 순서를 1로 기록

    while queue:  # 큐가 빌 때까지 반복
        node = queue.popleft()  # 큐에서 현재 노드를 꺼냄
        
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                cnt += 1
                order[neighbor] = cnt
                queue.append(neighbor)
            
# 6. BFS 시작
BFS(R)

# 7. 결과 출력
for i in range(1,N + 1):
    print(order[i])