[Python] 백준 24445번 - 알고리즘 수업 - 너비 우선 탐색 2

🔗 문제 링크

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

⏰ 소요된 시간

20분

문제를 제대로 보자^^!

🛡️ 난이도

실버 2

✨ 수도 코드

주의사항

• BFS로 인접 정점을 queue에 삽입할 때, 내림차순으로 삽입해야 한다.
• 입력받은 간선의 개수만큼 노드의 관계를 입력받아야 한다.

문제를 제대로 보지 않으면 쉽게 풀 문제도 오래 걸린다는...😩

전체 코드

from collections import deque
input = open(0).readline

num = 1
q = deque([])

def bfs(nodes, visited, num):
    while q:
        node = q.popleft()
        if not visited[node-1]:
            visited[node-1] = num
            num += 1
           # 내림차순으로 인접 정점 큐에 삽입
            for j in sorted(nodes[node-1], reverse=True):  
                q.append(j)
    return visited

node_cnt, edge_cnt, start_node = map(int, input().split())
nodes = [[] for _ in range(node_cnt)]
visited = [0 for _ in range(node_cnt)]

q.append(start_node)

# 노드 그래프 저장
for i in range(edge_cnt):
    a, b = map(int, input().split())
    nodes[a-1].append(b)
    nodes[b-1].append(a)

for n in bfs(nodes, visited, num):
    print(n)

정점을 방문하는 순서를 출력하는 것이므로 간단하게 visited에 방문 순서를 저장한다. 만약 방문하지 않은 정점은 0을 출력하여야 하는데, visited의 기본 세팅이 0이므로 딱 적절하다.