제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.
목차 :
- 그래프 탐색 알고리즘
- DFS
- BFS
그래프 탐색 알고리즘
코테 비율 40% 이상 유형 문제. 굉장히 중요한 유형임.
거의 무조건 코테에 한 문제 이상씩은 나온다 보면 됨.
그래프 자료구조는 탐색 알고리즘에 사용됨.
`그래프`라는 자료구조를 가지고, `그래프 탐색`이란 알고리즘을 설계할 것.
`그래프 탐색 알고리즘` : 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 찾는 알고리즘. 일종의 완전 탐색임.
깊이우선탐색과 너비우선탐색은 스택과 큐의 개념이 같이 들어감.
DFS : 스택(재귀) + 그래프
BFS : 큐(덱) + 그래프
DFS
모든 정점을 방문할 때 유리
(사실 모든 정점을 방문만 하는 경우는 큰 차이 없으나, 바텀을 찍어서 early return이 가능할 경우는 DFS가 더 나아보임. 바텀을 찍어야 하는 상황을 말하는 듯.)
/ 경우의 수, 순열과 조합(순서상관 유 무) 문제 해결에 유리
BFS에 비해 코드 구현이 간단
단, 모든 정점을 방문 필요 없거나, 최단거리 구할 땐 BFS가 유리.
각 정점을 방문했는지 여부를 판별할 visited 리스트가 필요. 처음엔 False로 다 초기화.
DFS의 실행 3단계(중요!!)
1. 시작 정점 방문 처리
2. 재귀하며 현재 정점에서 action 실행
3. 인접한 모든 정점들에 대해
4. 방문x 인접 정점으로 이동(함수 호출)
import sys
input = sys.stdin.readline
# DFS(깊이 우선 탐색)
'''
7 7
0 1
0 2
1 3
1 4
2 4
2 5
4 6
'''
# 정점 간선 개수가 첫 줄, 나머진 간선 정보
def dfs(node):
# 2. 현재 정점에서 action 실행
print(node, end = ' ')
# 3. 인접한 모든 정점들에 대해
for next_node in graph[node]:
# 4. 방문x 인접 정점으로 이동
if not visited[next_node]:
# 방문 처리 해줌 - 선 방문 처리 후 DFS호출
visited[next_node] = True
dfs(next_node)
n, m = map(int, input().split())
# 인접 리스트 생성
graph = [[] for _ in range(n)]
# 이미 방문한 노드 배열
visited = [False] * n
for _ in range(m):
# start, end 노드로 간선 정보 받기
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s) # 무방향 그래프
# 0번 노드에서 시작할거니까
# 1. 시작 정점 방문 처리
visited[0] = True
# DFS 실행
dfs(0)
# DFS 구현 방법은 반복과 재귀 두 가지가 있는데,
# 애초에 재귀 자체가 함수 콜이 메모리에 쌓이는 스택의 원리를 이용한 것이므로,
# 재귀를 사용해 DFS를 구현하는 것이 더 직관적이고 간결하다.
# 따라서, 수업에서도 재귀를 사용한 방법을 배울 것.
# 순수하게 실제 스택을 구현한 리스트를 사용할 경우는 반복을 이용한 방법이 그건데,
# 이 때는 인접한 걸 모두 스택에 넣고 시작하므로,
# 재귀의 함수 콜 스택과 살짝 느낌이 다름.
# DFS의 시간복잡도는, 수학적으로 증명하는 방법은 꽤나 어려움.
# 그래서, 우리는 직관적으로 이해할 건데,
# O(V + E)로 정해져 있음. O(정점개수 + 간선개수). BFS도 동일.
# 모든 정점과 간선을 한 번 이상씩은 웬만해선 탐색하게 되니까.
# 왜냐하면, 실제론 동일한 노드를 여러 번 방문하게 되니까 상수배가 되겠지만,
# 상수배는 무시해도 되니까 직관적으로 저정도는 됨.
# 단, 예외는 있음. 완전 그래프일 경우,
# 어떤 정점에서든지 나머지 정점들을 다 조회하게 되니까,
# 사실상 O(V^2)만큼 보게 되니까,
# 따라서 인접 리스트를 통해 구현했을 경우는 완전 그래프거나, 완전 그래프에 가까우면 O(V^2)이 나옴.
# 또한 애초에 인접 행렬을 써서 그래프를 구현했을 경우, 무조건적으로 O(V^2)가 나옴.BFS
정점 사이의 최단 경로를 찾거나, 여러 정점에서 동시에 탐색을 진행하는 문제에서 많이 사용함.
다익스트라는 간선들의 가중치가 다를 때, BFS는 가중치가 동일하거나 없을 때.
DFS와 달리 BFS는 조건에 맞는(가장 빠른 탈출구) 정점에 도달했을 때 탐색을 멈출 수 있어서 더 효율적.
완전탐색인건 똑같으니까 DFS도 저게 가능은 하나, 굉장히 비효율적. DFS는 처음에 도달한 경로가 최단 경로인지 확정을 못 하므로, 모든 경로를 다 탐색해 최소 거리를 구해야 함.
그러나 BFS는 DFS에 비해 구현이 복잡함.
얘는 queue를 사용해 구현해야함.
얘도 그 노드를 꺼내는(pop) 것 자체가 방문이라는 동작임.
BFS의 실행 3단계(중요!!)
1. 시작 정점 방문 처리
2. queue가 빌 때까지,
3. pop하며 현재 정점에서 action 실행
4. 인접한 모든 정점들에 대해
5. 방문x 인접 정점으로 이동(큐에 append)
from collections import deque
import sys
input = sys.stdin.readline
# BFS(너비 우선 탐색)
'''
7 7
0 1
0 2
1 3
1 4
2 4
2 5
4 6
'''
# 정점 간선 개수가 첫 줄, 나머진 간선 정보
def bfs(node):
# 얘는 재귀가 아니니까, bfs 함수는 한 번 호출만에 끝남.
queue = deque([node])
# 이제, queue에서 더 이상 꺼낼 게 없을 때까지 반복할거임.
# queue가 비어있단 건, 더 이상 갈 수 있는 곳이 없다는 것.
# 2. queue가 빌 때까지,
while queue:
# 얘는, dfs에서 호출이 방문이었던 것과 달리,
# 반복이 호출임.
# 3. pop하며 현재 정점에서 action 실행
node = queue.popleft()
print(node, end = ' ')
# 4. 인접한 모든 정점들에 대해ㅡ
for next_node in graph[node]:
if not visited[next_node]:
# 5. 방문x 인접 정점으로 이동(큐에 append)
visited[next_node] = True
queue.append(next_node)
n, m = map(int, input().split())
# 인접 리스트 생성
graph = [[] for _ in range(n)]
# 이미 방문한 노드 배열
visited = [False] * n
for _ in range(m):
# start, end 노드로 간선 정보 받기
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s) # 무방향 그래프
# 1. 시작 정점 방문 처리
visited[0] = True
bfs(0)과제 및 풀이 정리
- 그래프 탐색
- 바이러스
- 미로 찾기1
- 미로 찾기2
- 단지번호붙이기
- 타겟 넘버
- 게임 맵 최단거리
- 유기농 배추
- 나이트의 이동
- 안전 영역
- 산불 조심
- 토마토
- 토마토 3차원
- 벽 부수고 이동하기
