[항해99] 99클럽 코테 스터디 5일차 TIL + BFS(백준 24444번)

99클럽 코테 스터디 5일차 TIL + BFS(백준 24444)

오늘의 학습 키워드

- BFS(너비 우선 탐색)
- Queue, Deque
- 방문 순서 처리

공부한 내용

# 항해99 Day5
# 백준 24444번 알고리즘 수업 - 너비 우선 탐색

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

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

def BFS(graph, start, visited):
    queue = deque([start])
    visited[start] = 1 # 시작 정점의 방문 순서는 1
    cnt = 2 # 다음 방문할 정점의 순서는 2부터 시작

    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]: # 아직 방문하지 않은 정점이면
                visited[i] = cnt # 현재 카운트를 방문 순서로 기록
                cnt += 1 # 다음 방문할 정점의 순서 증가
                queue.append(i)

BFS(graph, R, visited)

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

1. BFS 알고리즘의 기본 구조

   • BFS는 큐를 사용하여 구현하고, 시작 정점부터 가까운 정점을 순서대로 방문

   • collections 모듈의 deque를 사용

     from collections import deque
     queue = deque([start])

2. 그래프 표현 방식

   • 인접 리스트를 사용하여 그래프 구현

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

3. 방문 순서 처리

   • visited 배열을 사용해서 각 정점의 방문 순서를 기록

   • 시작 정점은 1, 이후 방문하는 정점들은 2부터 순차적으로 증가

     visited = [0] * (N+1)
     visited[start] = 1 # 시작 정점
     cnt = 2 # 다음 방문할 정점의 순서

4. 오름차순 방문 처리

   • 인점 정점들을 오름차순으로 정렬

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

오늘의 회고

방문 순서를 기록하는 것에 익숙치가 않아서 시간이 많이 들었다. cnt 변수를 1부터 시작했다가 시작 정점과 첫 방문 정점의 순서가 겹치는 문제가 발생했고, cnt 변수를 2부터 시작해서 시작 정점(1)과 겹치지 않도록 수정하였다.
어제 DFS와 마찬가지로 BFS도 익숙치가 않아 문제 해결 방법이 바로바로 떠오르지 않는데 많이 풀어봐야할 것 같다.