그래프
1. 그래프란?
그래프는 정점(Node)과 간선(Edge)로 구성된 자료구조
❇️ 그래프의 종류
- 무방향 그래프
- 방향 그래프
- 가중치 그래프
- 사이클
2. 그래프 표현 방법
1) 인접 리스트
graph = [[] for _ in range(n)]
graph[0].append(1)
graph[1].append(0)➡️ 메모리 효율 좋음
📍 노드 수가 많으면 무조건 인접 리스트
2) 인접 행렬
graph = [[0]*n for _ in range(n)]
graph[0][1] = 1➡️ 장: 연결 여부 확인 빠름
➡️ 단: 메모리 큼
3. 그래프 탐색(BFS/DFS)
DFS(깊이 우선 탐색)
- 재귀, 스택
- 유형: 경로 탐색, 사이클 확인
def dfs(v):
visited[v] = True
for nxt in graph[v]:
if not visited[nxt]:
dfs(nxt)⭐ BFS(너비 우선 탐색)
- 큐
- 유형: 최단 거리 문제
from collections import deque
def bfs(start):
q = deque([start])
visited[start] = True
while q:
v = q.popleft()
for nxt in graph[v]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)4. 그래프에서 자주 출제되는 문제 유형
- 연결 요소 개수
- 최단 거리(BFS)
- 사이클 탐지
- 미로 탐색
- 섬 개수 문제
5. 핵심 예제
1) 연결 요소 개수
문제 느낌
정점 N개, 간선 M개가 주어질 때 연결된 덩어리가 몇 개인지?
왜 중요한가?
- DFS/BFS 기본 구조 그대로
- 방문 배열 관리 연습
- 이후 섬 개수, 네트워크 문제로 직결
👉 포인트
- 모든 노드를 순회하면서 방문 안 된 노드에서 DFS 시작
- DFS 한 번 = 연결 요소 하나
2) 사이클 탐지 (무방향 vs 방향 그래프 차이)
무방향 그래프
- 부모 노드만 제외하고 방문된 노드를 다시 만나면 사이클
방향 그래프
visited+recursion stack사용
왜 중요한가?
- 위상 정렬
- 순환 참조가 있는가? 류 문제의 뼈대
👉 포인트
- 무방향:
if visited[nxt] and next != parent - 방향: 방문 중 상태를 따로 관리
3) 최단 거리 BFS
문제 느낌
한 점에서 다른 모든 점까지의 최소 이동 횟수
dist = [-1] * n
dist[start] = 0👉 포인트
- 큐에 넣을 때 거리 갱신
dist[nxt] = dist[cur] + 1
4) 미로 탐색
문제 느낌
- 0은 벽, 1은 길
- 시작점에서 도착점까지의 거리
👉 포인트
- 좌표를 노드로 생각
- 범위 체크 + 방문 체크
트리
1. 트리란?
사이클이 없는 그래프
❇️ 트리 특징
- 노드 N개 ➡️ 간선 N-1개
- 루트 존재
- 부모 - 자식 관계
- 하나의 경로만 존재(유일)
2. 트리 용어 정리
- 루트 : 시작 노드
- 리프 : 자식 없는 노드
- 깊이 : 루트에서 거리
- 높이 : 가장 깊은 리프까지
- 서브트리 : 특정 노드를 루트로 하는 트리
3. 트리 탐색
1) DFS - 트리의 기본
def dfs(node):
for child in tree[node]:
dfs(child)2) 트리 순회(이진 트리)
- 전위: root ➡️ left ➡️ right
- 중위: left ➡️ root ➡️ right
- 후위: left ➡️ right ➡️ root
❇️ 후위 순회: 자식 계산 후 부모 처리하는 DP 문제
4. 트리에서 자주 출제되는 문제 유형
- 부모 찾기
- 트리 깊이
- 서브트리 크기
- 트리 DP
- LCA (최소 공통 조상)
5. 핵심 예제들
1) 부모 찾기
문제 느낌
- 루트가 1일 때 각 노드의 부모는?
👉 포인트
parent[child] = node- 방문 배열 없으면 무한 루프
2) 트리 깊이 구하기
문제 느낌
- 각 노드의 depth 출력
depth[child] = depth[node] + 13) 서브트리 크기
문제 느낌
- 각 노드를 루트로 하는 서브트리의 노드 개수
👉 포인트
size[node] = 1
for child in tree[node]:
size[node] += size[child]4) LCA(최소 공통 조상)
문제 느낌
- 두 노드의 가장 가까운 공통 조상
버전
- 단순: depth 맞추고 부모 따라가기
- 고급: binary lifting
