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

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

import sys; input=sys.stdin.readline
from collections import deque, defaultdict

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = 1
    order = 2

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if visited[neighbor] == 0:
                visited[neighbor] = order
                queue.append(neighbor)
                order += 1

n, m, r = map(int, input().split())
graph = defaultdict(list)
visited = [0] * (n+1)

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for adj_list in graph.values():
    adj_list.sort()

bfs(graph, r, visited)

print("\n".join(map(str, visited[1:])))

왜 이렇게 풀었을까?

• BFS를 활용하여 모든 정점을 방문하는 순서를 구해야하는 문제입니다.
• 이때 문제의 조건 중 간선의 개수가 최대 200,000개까지 입력될 수 있기 때문에 이를 효율적으로 처리하기 위해 간선들을 담는 리스트를 효율적으로 관리해야 했습니다.
  • 정점들의 관계를 동적으로 추가 가능케 하기 위해 defaultdict로 간선 리스트를 인접 리스트로 구현하였습니다.
• 문제에서 오름차순으로 방문하기를 원했기 때문에, 모든 정점의 인접 리스트를 정렬하는 과정이 포함되어 있습니다.
• 방문하지 않은 인접 노드들을 대상으로 그래프를 탐색하면서 방문 순서를 기록해 visited 배열에 담았습니다.
  • 이때 방문하지 못하는 노드들은 0으로 출력되어야하기 때문에 visited 배열의 원소들을 모두 0으로 초기화하였습니다.
• 기본적인 BFS에 방문 순서 + 정렬이 포함된 코드라고 보시면 될 것 같습니다. 이와 같이 BFS를 간단히 변형하는 문제도 최근 많이 출제되는 경향이 있어 연습을 많이 해둬야겠습니다.