Queue (2)
2024. 2. 17. 19:08ㆍ알고리즘
- BFS (Breath First Search)
그래프를 탐색하는 2가지 방법 → DFS / BFS
너비 우선 탐색은 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식을 말한다.
인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용하여 구현할 수 있다.
def BFS(G, v, n): # 그래프 G, 탐색 시작점 v
visited = [0] * (n + 1) # n : 정점의 개수
queue = [] # 큐 생성
queue.append(v) # 시작점 v를 큐에 삽입
visited[v] = 1
while queue: # 큐가 비어있지 않은 경우
t = queue.pop(0) # 큐의 첫번째 원소 반환
visit(t) # 할 일 수행
for i in G[t]: # t와 연결된 모든 정점에 대해
if not visited[i]: # 방문되지 않은 곳이라면
queue.append(i) # 큐에 넣는다
visited[i] = visited[t] + 1 # n 으로부터 1만큼 이동
이때
정점을 큐에 삽입하면서 visited에 방문 표시를 하는지
정점을 큐에서 빼면서 (pop) 방문 표시를 하는지
에 따라 큐에 정점이 중복하여 삽입될 가능성이 달라진다. 후자의 방법으로 pop 하면서 방문 표시를 하면 큐에 정점이 중복 삽입이 될 가능성이 생기고 큐의 크기가 정점의 개수에 맞춰있으면 큐 범위를 초과할 수도 있다. 따라서 삽입 시 if문을 걸어주거나 전자의 방법으로 방문 표시를 해야 한다.
BFS가 DFS보다 거리 관련 정보를 찾을 때 더 유용하다. (최단거리 찾는 등)
- 연습하기
# 7 8 # V개의 정점, E개의 간선
# 1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7 # 간선 정보
def bfs(s, v): # 시작정점, 정점 개수
q = [] # 큐 생성
visited = [0] * (v+1) # visited 생성
q.append(s) # 시작점 인큐
visited[s] = 1 # 시작점 방문표시
while q: # 큐가 비워질때까지... (남은 정점이 있으면)
t = q.pop(0)
# t에서 할 일
print(t)
for i in adjl[t]: # t에 인접한 정점들 꺼내기
if visited[i] == 0: # 방문하지 않은 정점이면
q.append(i) # 인큐
visited[i] = 1 + visited[t] # 방문표시 (그냥 1이 아니라 t 부터 온 거리를 추가)
print(visited)
V, E = map(int, input().split())
arr = list(map(int, input().split()))
# 인접리스트
adjl = [[] for _ in range(V+1)]
for i in range(E):
n1, n2 = arr[i * 2], arr[i * 2 + 1]
adjl[n1].append(n2)
adjl[n2].append(n1) # 무향그래프이므로 양쪽에 인접점 추가
bfs(1, V)
def bfs(s, v, g): # 시작정점, 정점 개수, 목적지
q = [] # 큐 생성
visited = [0] * (v+1) # visited 생성
q.append(s) # 시작점 인큐
visited[s] = 1 # 시작점 방문표시
while q: # 큐가 비워질때까지... (남은 정점이 있으면)
t = q.pop(0) # 처리할 정점을 디큐
# t에서 할 일 수행 (여기서는 목적지 도착했는지 점검 + 거리 구해놓기)
if t == g:
return visited[t] - 1 # 시작정점에서의 값이 1이라서 거리값을 구하려면 1을 빼줘야 함
for i in adjl[t]: # t에 인접한 정점에 대해
if visited[i] == 0: # 방문하지 않은 정점이면
q.append(i) # 인큐
visited[i] = 1 + visited[t] # 방문표시 (그동안 온 거리를 누적하여 합)
return 0 # g(목적지)까지 경로가 없는 경우 = while 문을 다 통과함
T = int(input())
for tc in range(1, T + 1):
V, E = map(int, input().split())
# 인접리스트
adjl = [[] for _ in range(V+1)]
for i in range(E):
n1, n2 = map(int, input().split())
adjl[n1].append(n2)
adjl[n2].append(n1) # 무향그래프이므로 양쪽에 인접점 추가
S, G = map(int, input().split())
print(f'#{tc} {bfs(S, V, G)}')
또한 지금까지는 시작정점을 하나로 두었지만, BFS는 시작정점이 여러 개여도 진행이 가능하다.
ex) 두 군데에서 방향제를 설치했을 때 전체에 향이 퍼지는 데 걸리는 시간
시작정점이 하나면 BFS 코드가 단순해져서 보통 심화문제로 가면 시작정점을 여러 개 준다.
- 그래프 탐색 시
- 그래프 정보 (인접 리스트로 저장)
- DFS (스택 등) , BFS (큐 등)
- 방문정보를 저장하기 위한 저장소 (인덱스를 활용한 리스트 등) → 정점 번호의 범위 필요
+ 출발점, 도착점 정보
'''
7 8
1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7
'''
V, E = map(int, input().split())
arr = list(map(int, input().split()))
G = [[] for _ in range(V + 1)]
for i in range(0, E*2, 2):
u, v = arr[i], arr[i + 1]
G[u].append(v)
G[v].append(u)
# 그래프 탐색
# 1. 그래프 정보(인접리스트)
# 2. DFS(스택), BFS(큐)
# 3. 방문정보를 저장하기 위해 저장소(정점 번호의 범위)
# 4. 출발점, 도착점 정보
D = [0] * (V + 1) # 출발점에서 해당정점까지 최단 거리
P = [0] * (V + 1) # 최단 경로 트리
Q = []
visited = [0] * (V + 1) # 정점번호 1부터 V까지 사용
v = 1 # 출발점
# 출발점을 큐에 삽입, 방문정보 표시
Q.append(v); print(v, end=' ')
visited[v] = 1
# 빈 큐가 아닐동안
while Q:
v = Q.pop(0)
# v의 인접정점(G[v])들 중에 방문하지 않은 정점(w)들 찾는다.
# v ----> w
for w in G[v]:
if visited[w] == 0:
visited[w] = 1; print(w, end=' ')
Q.append(w)
D[w] = D[v] + 1 # 출발점에 w까지의 최단거리가 확정
P[w] = v # 바로전에 방문한 정점 v 저장
print()
print(D[1:])
print(P[1:])