1. 기본 탐색
1-1. DFS
기본 구조
graph = []
visited = []
def dfs(now):
# 1. 현재 노드 방문 처리
visited[now] = True
# 2. 현재 노드와 인접한 노드를 확인
for nxt in graph[now]:
# 3. 아직 방문하지 않은 노드라면 더 깊이 들어감 (재귀)
if not visited[nxt]:
dfs(nxt)백트래킹
def backtracking(depth, path):
# 1. 종료 조건 (정답을 찾은 경우)
if depth == target_depth:
print(path)
return
# 2. 현재 단계에서 선택 가능한 후보들 탐색
for candidate in candidates:
# 3. 유망성 검사 (Constraint Check)
if is_promising(candidate):
# 4. 상태 변경 (선택)
visited[candidate] = True
path.append(candidate)
# 5. 다음 단계로 재귀 호출
backtracking(depth + 1, path)
# 6. 복구 (이게 백트래킹의 핵심!)
path.pop()
visited[candidate] = False1-2. BFS
기본 구조
from collections import deque
def bfs(start):
q = deque()
q.append(start)
visited = set()
visited.add(start_node)
while q:
now = queue.popleft()
for nxt in graph[now]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)deque를 사용하지 않을 경우
def bfs(start):
visited = [start]
q = [start]
idx = 0 # 큐의 현재 위치를 가리키는 포인터
# 포인터가 큐의 전체 길이보다 작을 때까지 반복
while idx < len(q):
now = q[idx]
idx += 1
for nxt in graph[now]:
if nxt not in visited:
visited.append(nxt)
q.append(nxt)변형 구조
플러드 필
최단 거리가 목적이 아니라 영역의 개수나 크기를 구하는 유형
count = 0
while q:
now = queue.popleft()
count += 1 # 한 칸씩 갈 때마다 카운트 증가
for nxt in graph[now]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)차원 확장
- 층을 구분하는 경우도 존재 - 벽 부수고 이동하기
- 층을 나누다 못해 아예 차원을 비트마스킹으로 다루는 문제도 있다 - 달이 차오른다, 가자
# 비트마스킹 비교
if not (keys & (1 << bit)):가중치
- 가중치가 0 또는 1인 경우 구분이 필요하다면 → 가중치가 0인 노드는 앞으로, 가중치가 1인 노드는 뒤로 보내는 식.
popleft()와pop()이 동시에 가능하다는 점을 이용
여러 지점에서 동시에 번져나가는 상황
- BFS를 시작하기 전, 모든 시작점 좌표를 미리 큐에 전부 넣고 시작
시작점과 도착점이 정해져 있을 경우
- 시작점과 도착점에서 동시에 출발하는 양방향 BFS - 퍼즐
- 경우의 수가 무지하게 많을 때 연산량을 줄이기 위해 사용
경로 복원이 필요할 경우 (역추적)
- 나를 여기로 보낸 직전 노드(parent)가 누군지 기록하는 배열을 만듦 (경로 리스트를 통째로 보내면 리스트 복사 비용 때문에 메모리와 시간이 초과될 가능성이 높음) - 숨바꼭질 4
상태 변환
- 2차원 배열을 문자열이나 정수 하나로 압축해 관리하는 기법
- 2차원 좌표
y, x→i = y*cols + x
- 2차원 좌표
2. 최단 경로
2-1. 다익스트라
2-2. 플로이드-워셜
2-3. 벨만-포드
2-4. 0-1 BFS
3. 연결성 및 구조
3-1. 위상 정렬
- 방향성이 있고 사이클이 없는 그래프(DAG, Directed Acyclic Graph)에서 노드들을 선후 관계를 유지하며 일렬로 나열하는 알고리즘.
- 진입 차수(Indegree): 특정 노드로 들어오는 간선의 개수
from collections import deque
def topological_sort(v, edges):
result = []
queue = deque()
indegree = [0] * (v + 1) # 진입 차수 배열
graph = [[] for _ in range(v + 1)]
# 1. 그래프 구축 및 진입 차수 계산
for a, b in edges:
graph[a].append(b)
indegree[b] += 1
# 2. 처음 시작할 때 진입 차수가 0인 노드를 큐에 삽입
for i in range(1, v + 1):
if indegree[i] == 0:
queue.append(i)
# 3. 큐에서 노드를 꺼내며 연결된 간선 제거
while queue:
now = queue.popleft()
result.append(now)
for neighbor in graph[now]:
indegree[neighbor] -= 1
# 새롭게 진입 차수가 0이 되면 큐에 삽입
if indegree[neighbor] == 0:
queue.append(neighbor)
# 4. 결과 확인 (방문한 노드가 V개보다 적으면 사이클이 존재한다는 뜻)
if len(result) < v:
return "Cycle Detected"
return result3-2. 유니온 파인드
- 합치고, 찾는 자료구조. 여러 노드 중 두 노드가 같은 그룹에 속해 있는지 판별할 때 사용한다.
def find(x):
# 경로 압축 (Path Compression)
# 루트 노드가 아니면, 루트 노드를 찾을 때까지 재귀적으로 호출하고 부모를 갱신함
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(parent, a)
root_b = find(parent, b)
# 두 대표자가 다르면 하나로 합침
if root_a != root_b:
# 보통 더 작은 번호의 노드를 부모로 설정하는 규칙을 많이 씀
if root_a < root_b:
parent[root_b] = root_a
else:
parent[root_a] = root_b
return True # 성공적으로 합쳐짐
return False # 이미 같은 집합임 (사이클 발생 가능성)재귀 깊이 제한이 걱정될 경우
def find_iterative(x):
root = x
# 1. 일단 대장(root)을 끝까지 찾아 올라감
while parent[root] != root:
root = parent[root]
# 2. 다시 x부터 올라가면서 만나는 모든 노드의 부모를 root로 통합
while parent[x] != root:
next_node = parent[x]
parent[x] = root
x = next_node
return root3-3. 최소 스패닝 트리
- 그래프 내 모든 정점들을 가장 적은 비용(간선의 가중치 합)으로 연결한 트리
- 간선이 적을 경우 크루스칼이 유리함 (정렬 비용이 크지 않기 때문에)
- 간선이 많을 수록 프림이 유리함 (정점 중심으로 움직임)
크루스칼 알고리즘
- 모든 간선을 가중치 기준으로 오름차순 정렬
- 가중치가 낮은 간선부터 그래프에 포함시킴
- 간선 추가할 때마다 사이클이 발생하는지 확인 ◀ 유니온 파인드
- 안 생기면 포함, 생기면 버림
import sys
# 유니온 파인드: 경로 압축(Path Compression) 적용
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(a, b):
root_a = find(parent, a)
root_b = find(parent, b)
if root_a != root_b:
parent[root_b] = root_a
return True
return False
def kruskal(v, edges):
# 1. 간선을 가중치 기준으로 오름차순 정렬
edges.sort(key=lambda x: x[2])
parent = [i for i in range(v + 1)]
mst_weight = 0
edges_count = 0
for u, v, weight in edges:
# 2. 사이클이 생기지 않는다면 간선 선택
if union(u, v):
mst_weight += weight
edges_count += 1
# 정점 - 1개의 간선을 찾으면 종료 (최적화)
if edges_count == v - 1:
break
return mst_weight프림 알고리즘
- 임의의 시작 정점을 정함
- 해당 정점과 연결된 간선 중 가장 가중치가 작은 간선을 선택해 포함
- 이미 트리에 포함된 정점과 연결된 모든 간선 중, 아직 방문하지 않은 정점으로 가는 가장 작은 정점을 트리에 포함 ◀ 우선순위 큐
- 모든 정점이 포함될 때까지 반복
import heapq
def prim(start_node, v, adj):
visited = [False] * (v + 1)
# (가중치, 정점) 형태로 우선순위 큐 관리
pq = [(0, start_node)]
mst_weight = 0
count = 0
while pq:
weight, curr = heapq.heappop(pq)
# 이미 방문한 정점이면 무시 (사이클 방지)
if visited[curr]:
continue
visited[curr] = True
mst_weight += weight
count += 1
if count == v: # 모든 정점을 방문했다면 종료
break
# 인접한 정점 중 방문하지 않은 곳을 큐에 삽입
for next_node, next_weight in adj[curr]:
if not visited[next_node]:
heapq.heappush(pq, (next_weight, next_node))
return mst_weight