BTS 아니고 BFS
드립력이 점점 약해지고 있지만, 난 괜챠나 댕댕댕댕..댕.....
뭔가 드립치고 싶어서 TIL 작성하는 것 같지만? 일단 해냈잖아?
백준 24444번 문제 풀이
문제
오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.
bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점
for each v ∈ V - {R}
visited[v] <- NO;
visited[R] <- YES; # 시작 정점 R을 방문 했다고 표시한다.
enqueue(Q, R); # 큐 맨 뒤에 시작 정점 R을 추가한다.
while (Q ≠ ∅) {
u <- dequeue(Q); # 큐 맨 앞쪽의 요소를 삭제한다.
for each v ∈ E(u) # E(u) : 정점 u의 인접 정점 집합.(정점 번호를오름차순으로 방문한다)
if (visited[v] = NO) then {
visited[v] <- YES; # 정점 v를 방문 했다고 표시한다.
enqueue(Q, v); # 큐 맨 뒤에 정점 v를 추가한다.
}
}
}[입력]
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.
문제 해석하기
- 너비우선 탐색 ⇒ deque를 사용해야 함. 큐!
- 무방향 그래프 ⇒ 결국 양방향이었음..
- 인접 정점은 오름차순으로 방문 ⇒ sort로 정렬하기
- 너비우선탐색이기 때문에
from collections import deque를 해주어 큐를 사용할 수 있도록 함 - n(정점),m(간선),r(시작정점) 입력받기
- import sys
- sys.stdlin.readline()을 이용해서 값을 입력받기
- 이 방법을 통해서 시간초과와 같은 문제를 해결할 수 있음
- cnt 생성하기
- 언제 접근했는지에 대한 정보를 저장하기 위한 변수 생성
- 간선 정보 입력받고, graph 생성하기
graph = [[] for i in range(n+1)]
for i in range(m):
u,v = map(int,input().split())
// 무방향그래프 => 양방향 그래프임
graph[u].append(v)
graph[v].append(u)- 방문한 정보를 visited를 이용해서 구현함
visited = [0] * (n+1)- 인접한 정점을 오름차순으로 방문하기 위해서 정렬 시도
for i in range(n+1):
graph[i].sort()- 입력받은 간선정보를 바탕으로 bfs 함수 생성
- 일단 함수가 실행됨과 동시에 큐에 우리가 접근하고자 하는 즉, 시작하는 정점을 넣어준다.
- 우리는 결국 어떤 정점이 언제 도착했는지에 대한 정보를 출력해야하기 때문에 cnt라는 변수를 이용해서 해당 정보를 저장해준다.
- visited[r]에 cnt를 추가하여 몇번째인지를 저장해준다.
cnt =1
def bfs(graph,r,visited):
global cnt
queue = dequeue([r])
visited[start] = cnt
cnt += 1- bfs 함수 내부의 내용
- queue가 빌때까지 탐색을 계속하도록 반복하는 while문을 구성한다.
- 일단 queue에서 하나의 원소를 뽑아서 출력한다.
- 뽑은 정점을 바탕으로, 해당 정점과 관련된 아직 방문하지 않은 정점을 큐에 삽입한다.
- 해당 정점에서 아직 방문하지 않은 정점들을 큐에 삽입해준다.
- bfs를 호출하기
- 위에서 받은 입력값들을 바탕으로 bfs를 호출하여 bfs 함수를 실행한다.
- cnt값을 바탕으로 print하기
for i in range(n+1):
if i!=0:
print(visited[i]) 문제 풀이 중 문제점
1) 무방향 그래프란
처음에는 무방향 그래프가 단순히 한쪽으로만 연결된 그래프라고 생각했는데, 왼쪽에서 오른쪽 노드로만 접근하는 것이 아니라 아예 연결되어있기때문에 방향성이 없어서 어느 방향으로든 이동할 수 있는 것을 의미한다.
무방향 그래프 == 양방향 그래프라는 걸 깨닫고 다시 코드를 작성해준다.2) sort 잊지 말기
위에서 생각할때 sort를 써두고서는 정작 코드를 제출할때는 잊고 작성을 안했다.. sort로 정렬해서 인접정점에 오름차순으로 접근할 수 있도록 잊지말자!
import sys
from collections import deque
input = sys.stdin.readline
# 정점의 수 n, 간선의 수 m, 시작 정점 r 입력
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) # 양방향 그래프이므로 반대 방향도 추가
# 방문 순서를 기록하기 위한 리스트
visited = [0] * (n + 1)
cnt = 1 # 방문 순서 기록용
# BFS 함수
def bfs(graph, start, visited):
global cnt
queue = deque([start])
visited[start] = cnt # 시작 정점 방문 표시
cnt += 1
while queue:
v = queue.popleft()
for i in sorted(graph[v]): # 정점 번호가 작은 것부터 방문
if not visited[i]:
visited[i] = cnt
cnt += 1
queue.append(i)
# BFS 탐색 실행
bfs(graph, r, visited)
# 결과 출력
for i in range(1, n + 1): # 1부터 n까지의 방문 순서 출력
print(visited[i])
BFS란?
일단 BFS가 무엇인지에 대해서 알고 넘어가는것이 좋을 것 같아서 내용 정리를 해보았다.
- BFS(Breadth-First Search) 는 너비 우선 탐색 알고리즘으로, 그래프나 트리의 모든 정점을 탐색할 때 사용된다
- BFS는 시작 정점에서부터 가까운 정점들을 먼저 방문한 후, 그다음으로 먼 정점들을 순차적으로 탐색하는 방식이다
- 이 알고리즘은 주로 최단 경로 탐색이나 레벨 탐색에 사용됩니다.
BFS의 동작 방식
- 시작 정점 선택: 탐색을 시작할 초기 정점을 선택
- 큐 초기화: 탐색할 정점을 보관하기 위해 큐(Queue)를 초기화하고, 시작 정점을 큐에 삽입
- 방문 처리: 시작 정점을 방문했음을 표시하고, 방문 순서를 기록
- 큐에서 정점 추출 및 인접 정점 삽입: 큐에서 정점을 꺼내고, 그 정점에 인접한 모든 정점을 순서대로 탐색한다. 아직 방문하지 않은 정점들을 큐에 삽입하고, 방문 처리
- 반복: 큐가 빌 때까지 이 과정을 반복
- 종료: 큐가 비어 있으면 탐색이 종료
BFS의 특성
- 자료구조: BFS는 큐(Queue)를 사용하여 탐색한다
- 방문 순서: 먼저 탐색한 정점의 인접 정점들을 차례대로 탐색하므로, 시작 정점과 가까운 정점부터 탐색한다
- 시간 복잡도: BFS의 시간 복잡도는 O(V+E), 여기서 V는 정점의 개수,E는 간선의 개수
- 최단 경로: 가중치가 없는 그래프에서 시작 정점으로부터 다른 정점까지의 최단 경로를 구할 있다.
오늘의 회고
깊이우선탐색과 더불어 너비우선탐색 알고리즘에 대해 공부하다보니 확실히 두개의 알고리즘이 연관성이 있어서 문제 풀이가 훨씬 쉬웠던 것 같다. 이번 공부를 통해서 dfs와 bfs에 대해 잘 알 수 있었던 시간이었다.
