[백준/Python] 24444 알고리즘 수업 - 너비 우선 탐색 1

📌문제 탐색하기

• N(5 ≤ N ≤ 100,000)개의 정점과 M(1 ≤ M ≤ 200,000)개의 간선으로 구성된 무방향 그래프가 주어진다.
  • 정점 번호는 1번부터 N번, 모든 간선의 가중치는 1
• 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서 출력하기
  • 인접 정점은 오름차순으로 방문

주어진 조건에 따라 BFS 탐색하며 각 노드를 방문할 때마다 몇번째로 방문했는지 체크하면 된다.

 

---

📌코드 설계하기

1. 정점의 수 N, 간선의 수 M, 사적 정점 R을 입력받는다.
2. 간선 정보를 입력받아 인접 리스트 graph에 저장한다.
3. graph의 각 요소들을 오름차순 정렬한다.
4. deque를 사용해 q를 만들어 R을 저장한다.
5. 방문 여부를 관리할 visited를 만들어 0으로 초기화하고, R번째 요소에는 1을 저장한다.
6. visited_order를 2로 초기화한다.
7. q가 빌때까지 아래 과정을 반복한다.
   1. q에서 가장 앞쪽의 요소를 꺼낸다.
   2. 꺼낸 노드와 인접한 정점을 오름차순 탐색한다.
   3. 인접한 정점이 현재 방문하지 않은 곳이라면, visited에 방문 순서를 기록 후 visited_order에 1을 더하, q의 맨 뒤에 추가한다.
8. 탐색이 종료된 후 각 정점들의 방문 순서를 visited를 토대로 출력한다.

 

---

📌정답 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort()

q = deque([R])
visited = [0]*(N+1)
visited[R] = 1
visited_order = 2

while q:
    cur_node = q.popleft()
    for next_node in graph[cur_node]:
        if not visited[next_node]:
            q.append(next_node)
            visited[next_node] = visited_order
            visited_order += 1

print(*visited[1:], sep="\n")