[TIL] 99클럽 코테 스터디 5일차 TIL - BFS : <백준 24444 알고리즘 수업 - 너비 우선 탐색 1> 문제풀이 with python

Today's keyword : BFS

 

📌 개념 설명

BFS(너비 우선 탐색) 

• BFS는 그래프 탐색 알고리즘 중 하나로, 시작 정점에서 인접한 정점들을 먼저 방문한 후, 그 정점의 인접한 정점들을 탐색하는 방식입니다. 즉, "너비"를 우선적으로 탐색합니다.
• BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 큐는 FIFO(First In First Out) 방식으로 작동하여, 먼저 들어온 정점이 먼저 나가게 됩니다.

 

📌 문제 설명

https://www.acmicpc.net/problem/24444

이 문제는 주어진 그래프에서 너비 우선 탐색(BFS)을 수행하고, 각 정점의 방문 순서를 출력하는 문제입니다.

입력

• 첫 번째 줄에 정점의 수 n, 간선의 수 m, 시작 정점 r이 주어집니다.
• 다음 m개의 줄에는 간선 정보가 주어지며, 각 줄은 두 정점 a와 b를 나타냅니다. 이는 a와 b가 연결되어 있음을 의미합니다.

출력

• 각 정점에 대해 방문 순서를 출력합니다. 방문하지 않은 정점은 0으로 표시합니다.

 

📌 문제 풀이

import sys
from collections import deque

input = sys.stdin.readline
n, m, r = map(int, input().split())
graph = [[] for i in range(n + 1)]

# m개의 간선 정보 입력받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)  # a에서 b로의 간선 추가
    graph[b].append(a)  # b에서 a로의 간선 추가 (양방향)

# 각 정점의 인접 리스트를 오름차순으로 정렬
for i in range(1, n + 1):
    graph[i].sort()

visited = [0] * (n + 1)
queue = deque()
visit_order = 1

def bfs(graph, v, visited):
    global visit_order
    queue.append(v)

    while queue:
        i = queue.popleft()
        if visited[i] == 0:
            visited[i] = visit_order
            visit_order += 1
            for j in graph[i]:
                if visited[j] == 0:  # 방문하지 않은 정점만 추가
                    queue.append(j)

bfs(graph, r, visited)

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

1. 그래프 초기화:

• 정점 수 n, 간선 수 m, 시작 정점 r을 입력받아 그래프를 초기화합니다.
• 인접 리스트 형태로 그래프를 표현하기 위해 graph 리스트를 생성합니다.

2. 간선 정보 입력:

• m개의 간선 정보를 입력받아 그래프에 추가합니다. 양방향 간선이므로 두 정점 모두에 대해 연결을 추가합니다.

3. 정점 정렬

• 각 정점의 인접 리스트를 오름차순으로 정렬하여, BFS 탐색 시 정점이 작은 순서대로 방문되도록 합니다.

4. BFS 구현:

• BFS를 수행할 bfs 함수를 정의합니다. 이 함수는 큐를 사용하여 현재 정점을 방문하고, 인접한 정점들을 큐에 추가합니다.
• 방문할 때마다 visited 리스트에 현재 방문 순서를 기록합니다.

5. BFS 호출 및 결과 출력

• 시작 정점 r에서 BFS를 호출하고, 각 정점의 방문 순서를 출력합니다.

 

📌 주의사항

1. Deque 사용

  큐를 사용하기 위해서는 오른쪽에 삽입(append)하고 왼쪽에서 추출(popleft)해야 하기 때문에  앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형인 deque를 이용합니다. deque는 collections 패키지의 deque 클래스를 가져와 사용할 수 있습니다.

from collections import deque

2. 방문한 정점은 큐에 추가하지 않기 

 정점을 큐에 삽입할 때 방문하지 않은 정점만 추가하도록 해야 시간초과가 나지 않습니다. 

            for j in graph[i]:

                if visited[j] == 0:  # 방문하지 않은 정점만 추가하도록 조건 설정

                    queue.append(j)

처음에 해당 조건 없이 추가해서 시간초과가 났었고, 그 결과를 확인해보면 정점과 연결된 노드들을 또 큐에 추가하여 쓸데없이 연산 과정이 길어졌음을 알 수 있습니다.

deque([1])
1 [0, 1, 0, 0, 0, 0]
deque([2, 4])
2 [0, 1, 2, 0, 0, 0]
deque([4, 1, 3, 4])
4 [0, 1, 2, 0, 3, 0]
deque([1, 3, 4, 1, 2, 3])
deque([3, 4, 1, 2, 3])
3 [0, 1, 2, 4, 3, 0]
deque([4, 1, 2, 3, 2, 4])
deque([1, 2, 3, 2, 4])
deque([2, 3, 2, 4])
deque([3, 2, 4])
deque([2, 4])
deque([4])

3. sys.stdin.readline 사용 

input()으로만 작성하게 될 경우 시간초과가 나기 때문에 input = sys.stdin.readline 을 통해 입력을 빠르게 처리합니다. input() 함수는 입력을 받을 때마다 입력을 받고 문자열을 처리하고 공백을 제거한는 등의 여러 단계를 거치며 입력을 처리합니다. 반면, sys.stdin.readline은 한 번에 전체 줄을 읽고 메모리에 저장하기 때문에 속도가 빠릅니다. 

 

 

 

오늘의 회고 

• 시간 초과가 나지 않게 하기

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL