99클럽 코테 스터디 5일차 BFS(너비 우선 탐색)

Seongbin·2024년 11월 2일

99클럽 코테 스터디

목록 보기

5/24

오늘의 학습 키워드

BFS, Breadth-First Search(깊이 우선 탐색)

이번엔 dfs 정리한 것을 바탕으로 bfs를 정리!!!

그래프 탐색이란?

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

그러면 BFS란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
- 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
- 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

너비 우선 탐색(BFS)의 특징

직관적이지 않은 면이 있다.
BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
BFS는 재귀적으로 동작하지 않는다.
이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색
일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.

너비 우선 탐색(BFS)의 과정

노드(시작 노드)를 방문한다. (방문한 노드 체크)

큐에 방문된 노드를 삽입(enqueue)한다.
초기 상태의 큐에는 시작 노드만이 저장
- 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.

큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.

큐에서 꺼낸 노드를 방문한다.
큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
- 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
큐에 방문된 노드를 삽입(enqueue)한다.

큐가 소진될 때까지 계속한다.

코드로 적용해보기

1번 노드에서 시작하여 방문하고, 인접한 모든 노드를 큐에 넣습니다.
큐 상태: [2, 3]
큐에서 2번 노드를 꺼내 방문하고, 인접한 모든 노드를 큐에 넣습니다.
큐 상태: [3, 6, 4]
큐에서 3번 노드를 꺼내 방문하고, 인접한 모든 노드를 큐에 넣습니다.
큐 상태: [6, 4, 7, 5]
큐에서 6번 노드를 꺼내 방문합니다. 6번은 더 이상 방문할 인접 노드가 없습니다.
큐 상태: [4, 7, 5]
큐에서 4번 노드를 꺼내 방문합니다. 4번도 더 이상 방문할 인접 노드가 없습니다.
큐 상태: [7, 5]
큐에서 7번 노드를 꺼내 방문합니다. 7번도 더 이상 방문할 인접 노드가 없습니다.
큐 상태: [5]
마지막으로 5번 노드를 큐에서 꺼내 방문합니다. 5번도 더 이상 방문할 인접 노드가 없습니다.
큐 상태: []
큐가 비었으므로 BFS 탐색이 끝났습니다.

BFS 탐색 순서는 다음과 같습니다: 1 -> 2 -> 3 -> 6 -> 4 -> 7 -> 5

from collections import deque

def bfs(graph, start):
    # 방문한 노드를 기록하기 위한 리스트
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()  # 큐에서 첫 번째 노드를 꺼냄
        print(v, end=' ')

        # 현재 노드와 연결된 노드를 모두 확인 (번호가 낮은 순서부터 처리)
        for i in sorted(graph[v]):
            if not visited[i]:
                queue.append(i)  # 방문하지 않은 노드는 큐에 추가
                visited[i] = True

# 그래프 정보 (DFS 코드와 동일)
graph = [
    [],         # 0번 노드는 사용하지 않음
    [2, 3, 7],  # 1번 노드는 2, 3, 7번 노드와 연결
    [1, 4, 6],  # 2번 노드는 1, 4, 6번 노드와 연결
    [1, 5, 7],  # 3번 노드는 1, 5, 7번 노드와 연결
    [2, 6],     # 4번 노드는 2, 6번 노드와 연결
    [3, 7],     # 5번 노드는 3, 7번 노드와 연결
    [2, 4],     # 6번 노드는 2, 4번 노드와 연결
    [1, 3]      # 7번 노드는 1, 3번 노드와 연결
]

print("방문 순서:")
bfs(graph, 1)

출력 :
방문순서
1 2 3 6 4 7 5

graph 변수는 그래프를 인접 리스트(adjacency list) 방식으로 표현
인접 리스트는 그래프를 저장하는 방법 중 하나로, 각 노드에 연결된 다른 노드들을 리스트 형태로 저장
이 방식은 메모리 효율성이 좋아서, 그래프의 간선 수가 많지 않을 때 특히 유용합니다. 즉, 그래프가 희소할 때 (즉, 간선의 수가 적을 때) 메모리 사용량이 효율적이며, 간선의 수가 많을 때는 인접 행렬 방식보다 비효율적일 수 있습니다.

BFS 함수

graph와 start를 인자로 받아 시작 노드에서부터 너비 우선 탐색을 진행
visited 리스트는 각 노드가 방문되었는지를 기록하기 위한 것으로, 노드의 수만큼 False로 초기화합니다.
deque를 이용해 큐를 구현하였고, 시작 노드를 큐에 추가하고 visited 리스트에 방문 표시를 합니다.

탐색 과정

while queue: 반복문은 큐가 빌 때까지 실행됩니다.
v = queue.popleft()는 큐에서 첫 번째 노드를 꺼내어 현재 방문 중인 노드를 기록합니다.
for i in sorted(graph[v]):는 현재 노드 v와 연결된 모든 노드를 번호가 낮은 순서대로 확인하는 루프입니다.
방문하지 않은 노드를 큐에 추가하고 방문 표시를 합니다.

오늘의 문제

백준 24444번

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

문제 설명

입출력 예

문제 생각해보기

위 입출력 예시에 따르면 결론적으로 5개의 정점, 5개의 간선인데

1 ~ 4까지의 노드 중 1번과 3번 사이 간선이 없다.
그리고 5번 노드는 아무 노드와 연결되어 있지않다.

BFS 탐색 순서

오름차순 방문: BFS 탐색 시 인접 정점들을 오름차순으로 방문.

시작 노드는 1번이다. 1번을 방문했으므로 방문 순서는 1.
노드 1에 연결된 노드는 2와 4이다. 오름차순으로 방문하므로 2번을 먼저 큐에 넣고, 이어서 4번을 큐에 넣는다.
큐에서 2번을 꺼내 방문했으므로 방문 순서는 2.
- 노드 2에 연결된 노드는 1, 3, 4이다. 이미 1번은 방문했으므로 3번을 큐에 추가하고, 4번은 이미 큐에 있으므로 추가하지 않는다.
큐에서 4번을 꺼내 방문했으므로 방문 순서는 3.
- 노드 4에 연결된 노드는 1, 2, 3이다. 이미 1번과 2번은 방문했으므로 3번은 이미 큐에 있으므로 추가하지 않는다.
큐에서 3번을 꺼내 방문했으므로 방문 순서는 4.
노드 3에 연결된 노드는 2와 4이다. 이미 둘 다 방문했으므로 더 이상 추가할 노드가 없다.
노드 5는 연결된 간선이 없어서 방문할 수 없음. 따라서 방문 순서는 0.

따라서 BFS 탐색 순서는 1 -> 2 -> 4 -> 3이며, 5번 노드는 방문할 수 없기 때문에 방문 순서는 0이다.

1. 기본 설정 및 입력 처리

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split())  # 정점의 수, 간선의 수, 시작 정점
graph = [[] for _ in range(n + 1)]  # 인접 리스트로 그래프 표현
visited = [0] * (n + 1)  # 각 정점의 방문 순서를 저장하는 리스트 (0이면 방문하지 않음)

import sys와 sys.setrecursionlimit(10 ** 6) : 이 코드는 재귀 깊이를 설정하여 스택 오버플로를 방지하는데 사용되며 DFS에서 필요. 하지만 BFS에서는 사용하지 않아도 됨.
input = sys.stdin.readline : 입력을 빠르게 처리하기 위한 코드
n, m, r = map(int, input().split()): 입력에서 정점의 수(n), 간선의 수(m), 시작 정점(r)을 받음.
graph = [[] for _ in range(n + 1)]: 그래프를 인접 리스트로 표현. 정점 번호는 1부터 시작하므로 크기를 n+1로 설정하여 사용하지 않는 0번 인덱스를 포함
visited = [0] * (n + 1): 각 정점의 방문 순서를 저장할 리스트. 모든 정점을 아직 방문하지 않았으므로 초기값은 0으로 설정.

2. 너비 우선 탐색 (BFS) 함수 정의

order = 1  # 방문 순서 카운터
def bfs(graph, start, visited):
    global order
    queue = deque([start])
    visited[start] = order  # 시작 정점 방문 표시 및 순서 기록
    
    while queue:
        v = queue.popleft()  # 큐에서 첫 번째 노드를 꺼냄
        for i in graph[v]:  # 현재 노드와 연결된 모든 인접 노드를 확인
            if visited[i] == 0:  # 아직 방문하지 않은 노드라면
                queue.append(i)  # 큐에 추가
                order += 1
                visited[i] = order  # 방문 순서 기록

order = 1 : 방문 순서를 나타내는 카운터 변수. 시작 정점을 방문할 때 1로 설정.
bfs(graph, start, visited) : 그래프, 시작 정점, 방문 리스트를 인자로 받아 BFS를 수행.
queue = deque([start]) : deque를 사용하여 큐를 생성하고, 시작 정점을 큐에 넣음.
visited[start] = c: 시작 정점을 방문했음을 표시하고 방문 순서를 기록.
while queue: : 큐가 빌 때까지 반복.
v = queue.popleft() : 큐에서 첫 번째 노드를 꺼내 현재 방문 노드로 설정.
for i in graph[v]:: 현재 노드와 연결된 모든 인접 노드를 확인.
if visited[i] == 0: : 아직 방문하지 않은 노드라면 큐에 추가하고 방문 순서를 기록.

3. 간선 정보 입력 및 그래프 구성

	for i in range(m):
    a, b = map(int, input().split())  # 간선 정보 입력
    graph[a].append(b)
    graph[b].append(a)  # 무방향 그래프이므로 양쪽에 간선 추가

for i in range(m) : m개의 간선 정보를 입력받음
append()는 파이썬의 리스트(list) 자료형에서 사용되는 메서드로, 리스트의 끝에 새로운 요소를 추가하는 역할
graph[a].append(b): 정점 a의 인접 리스트에 정점 b를 추가.
graph[b].append(a): 정점 b의 인접 리스트에 정점 a를 추가.

입력 예시에 따르면

graph[1]에 4와 2를 추가 → graph[1] = [4, 2]

graph[2]에 1, 3, 4를 추가 → graph[2] = [1, 3, 4]

graph[3]에 2와 4를 추가 → graph[3] = [2, 4]

graph[4]에 1, 2, 3을 추가 → graph[4] = [1, 2, 3]

4. 인접 리스트 정렬

for i in range(n + 1):
    graph[i].sort()  # 오름차순으로 인접 정점을 정렬

5. 너비 우선 탐색 시작 및 결과 출력

bfs(graph, r, visited)

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

bfs(graph, r, visited) : 시작 정점 r에서 DFS 수행
print(visited[i]) : 정점 i의 방문 순서를 출력

전체 풀이

import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 정점
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1) # 방문 순서 저장. 0이면 방문 X

order = 1 # 순서
def bfs(graph, start, visited):
    global order
    queue = deque([start])
    visited[start] = order # 방문하면 순서 나타내기
    
    while queue:
        v = queue.popleft()
        for i in graph[v]: # 인접 노드 중
            if visited[i] == 0: # 방문하지 않은 노드 큐에 추가
                queue.append(i)
                order += 1 # 순서+1
                visited[i] = order

# m개의 연결된 간선 정보 입력받기
for i in range(m):
    a, b = (map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1): # 인접노드 정보 오름차순 정렬
    graph[i].sort()
# print(graph)

bfs(graph, r, visited)

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