개념
그래프 탐색
- 하나의 정점에서 시작하여 모든 정점을 한 번씩 방문하여 처리하는 연산
- 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다.
- 예 : 도로망에서 특정 도시에서 다른 도시로 갈 수 있는지 여부
특징
- 갈 수 있는곳 까지 계속 진행, 더 진행할 수 없으면 돌아온뒤 다시 탐색
- queue를 활용(deque를 사용하는게 시간복잡도 면에서 훨씬 더 효율적이다.)
- BFS는 재귀적으로 동작하지 않는다.
- 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
- 검사하지 않을경우 무한루프에 빠진다.
- ‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.
원리
- 시작 정점 v를 방문
- v에 인접한 모든 정점들을 방문
- 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문
→ 큐 이용
알고리즘
- a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
- 큐에 방문된 노드를 삽입(enqueue)한다.
- 초기 상태의 큐에는 시작 노드만이 저장
- 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
- 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
- 큐에서 꺼낸 노드를 방문한다.
- 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
- 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
- 큐에 방문된 노드를 삽입(enqueue)한다.
- 큐가 소진될 때까지 계속한다.
vs DFS
장점
- 답이 되는 경로가 여러개인 경우에도 최단 경로임을 보장한다.
- 최단 경로가 존재한다면 깊이가 무제한 깊어지더라도 답을 찾을 수 있다.
단점
- 경로가 길 경우에는 탐색가지가 급격하게 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다. (큐의 특성?)
- 해가 존재하지 않으면
- 유한 그래프 - 모든 그래프를 탐색후 실패로 끝남
- 무한 그래프 - 끝내지 못한다.
시간복잡도
- 인접 행렬로 표현한 경우 시간 복잡도
• O(n^2) - 인접 리스트로 표현한 경우 시간 복잡도
• O(n+e)
필기
- DFS , BFS 모두 방문기록을 활용하는 방식이다. → visit(), visit[i][j] 방문 기록을 남기는 방향으로 문제를 푸는 유형이다.
- DFS에 조건을 거는데, break은 특이사항이 아니라면 거의 없다. (대부분 countinue를 사용
- pop의 시간복잡도는 O(n), popleft()의 시간 복잡도는 O(1)
- if문이 끝나면 재귀문은 알아서 끝난다.
- dfs의 큰 틀은 항상 똑같다. 여차하면 외우는게 좋을지도 모른다.
- n x m 행렬문제는 dy, dx를 활용해 다음위치를 생각한다 항상.
- dfs의 유형은 크게 2가지로 나눌 수 있다.
-
최단 거리를 구해야 하는 경우
일반적인 bfs로 구현이 가능하다. 큐를 활용해 단개별 정점들을 탐색해 주면 된다.
-
최단 거리를 구하지만, 조건이 여러개 존재하는 경우 ( 방문한 지점도 다시 방문가능 등)
일반적인 방법이 아니기 떄문에, dfs알고리즘을 약간 변형해야한다. 기존에 방문했던 정점이라도, 최소 비용으로 업데이트가 가능하다면 큐에 새로 추가한다.
관련 문제 - https://www.acmicpc.net/problem/9466
-
코드
- 수도코드
bfs(G, v)
Q ← createQueue()
G.visited[v] ← TRUE
enqueue(Q, v)
visit(v)
while (not isEmpty(Q)) do
v ← dequeue(Q)
for all w ∈ (v의 인접 정점) do
if w가 방문되지 않았으면 then
enqueue(Q, w.vertex)
G.visited[w.vertex] ← TRUE
visit(w.vertex)
end bfs()- bfs
from collections import deque
def bfs(graph, v, visited, pred):
global result
q = deque([v])
# 현재 정점을 방문 처리
visited[v] = True
# 큐가 빌 때까지 반복
while q:
v = q.popleft()
result.append(v)
# 현재 정점의 인접 정점 모드 큐에 삽입, 방문
for i in range(7):
if graph[v][i] and (not visited[i]):
q.append(i)
visited[i] = True- 백준 1260 풀이
from collections import deque
# n: 정점의 개수, m: 간선의 개수, v:탐색을 시작할 정점의 번호
n, m, v = map(int,input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
graph[a].sort()
graph[b].sort()
def bfs(graph, start, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드를 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
# 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
for k in graph[v]:
if not visited[k]:
queue.append(k)
visited[k] = True
visited = [False] * (n+1)
bfs(graph, v, visited)참고자료
해보자! 게임 클라 개발자!