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

 

 

문제

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

 

 

작성한 코드

import sys
from collections import deque
input = sys.stdin.readline

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
order = 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()

def bfs(v):
    global order
    q = deque([v])
    visited[v] = order

    while q:
        e = q.popleft()
        for i in graph[e]
            if visited[i] == 0:
                order += 1
                q.append(i)
                visited[i] = order
    
bfs(R)

for i in range(1, N+1):
    print(visited[i])

cf.) 너비 우선 탐색 → Queue 사용!

cf.) 파이썬에서 Queue를 이용하기 위해서는 from collections import deque 를 통해 deque를 사용해야 한다.

 

- N : 정점 수 / M : 간선 수 / R : 시작점 / order : 순서를 나타내는 변수

- graph : 연결 정보 리스트 / visited : 방문 순서 리스트

- graph & visited 에서 N+1을 사용한 이유? → 노드 번호와 인덱스를 맞추기 위해서!

- 간선 수 만큼 for문을 돌려 노드 별 연결된 정보를 공백을 기준으로 입력받고, 리스트 graph에 연결 정보를 추가해준다.

- 이후에 리스트 graph를 오름차순으로 정렬해준다.

 

- bfs 함수를 선언

  → 너비 우선 탐색을 하기 위해 필요한 Queue인 q에 v를 넣어서 시작한다.

  → 노드 v에 대해서 몇 번째로 방문했는지 값을 저visited에 저장한다.

  → 큐 q가 빌 때까지 반복한다.

  → 큐에서 가장 왼쪽에 있는 원소를 popleft()를 통해 빼서 e에 저장한다.

  → for문을 통해 e번 인덱스에 연결된 원소들을 확인한다.

  → 아직 방문하지 않은 인접 원소들을 큐에 삽입하고, order의 값을 1씩 증가하여 visited에 순서를 나타낸다.

- 최종적으로 인덱스 1부터 N까지의 visited 값을 출력한다. (0번 인덱스는 제외)