LeetCode 133 Clone Graph 풀이: 방문 매핑을 사용하는 그래프 DFS
LeetCode 133 Clone Graph를 원본 노드와 복제 노드의 매핑을 이용한 DFS로 푼다. 복제 노드를 이웃 탐색 전에 저장해 순환을 처리하고 독립된 그래프를 만드는 과정을 다룬다.
#그래프
노드와 간선의 관계를 탐색하고 복사하는 그래프 알고리즘 문제를 다룬다. 현재 4개의 풀이가 있다.
LeetCode 130 Surrounded Regions 풀이: 경계 연결 영역을 보존하는 BFS
LeetCode 130 Surrounded Regions에서 가장자리의 O와 연결된 영역을 BFS로 표시하고, 남은 O를 X로 바꾼다. 격자를 제자리에서 수정해 O(mn) 시간에 처리한다.
프로그래머스 가장 먼 노드 풀이: 인접 리스트 BFS
1번 노드에서 BFS로 모든 노드까지의 최단 간선 거리를 구한다. 최댓거리와 같은 거리를 가진 노드 수를 세는 풀이를 설명한다.
프로그래머스 순위 풀이: 승패 전이 관계를 확정하는 플로이드-워셜
프로그래머스 순위에서 경기 결과를 방향 그래프로 나타내고 플로이드-워셜로 간접 승패 관계를 구한다. 승리·패배 수의 합으로 순위를 확정할 수 있는 선수를 찾는다.
그래프 학습 가이드
필요한 주제만 펼쳐서 그래프의 핵심 개념을 익힌다.
그래프 기본 개념
그래프는 대상 사이의 관계를 노드와 간선으로 표현하는 자료구조다.
- 노드: 도시, 사람, 상태처럼 관계의 대상이 되는 단위
- 간선: 두 노드 사이의 연결 관계
- 방향 그래프: 간선마다 이동 방향이 있는 그래프
- 가중치 그래프: 간선마다 거리나 비용이 붙은 그래프
- 사이클: 시작 노드로 돌아오는 경로
문제에서 도시와 도로, 사람과 친구 관계, 작업과 의존성이 등장하면 그래프로 모델링할 수 있는지 먼저 확인한다.
그래프 표현 방식
코딩 테스트에서는 입력 크기와 간선 수에 따라 그래프 저장 방식을 고른다.
| 표현 | 특징 | 적합한 상황 |
|---|---|---|
| 인접 리스트 | 각 노드에서 연결된 노드만 저장 | 간선이 적거나 일반적인 탐색 문제 |
| 인접 행렬 | 두 노드의 연결 여부를 표에 저장 | 노드 수가 작고 연결 여부를 자주 확인하는 문제 |
| 간선 목록 | 간선을 `(출발, 도착, 비용)` 형태로 저장 | 간선 자체를 정렬하거나 순회하는 문제 |
노드 수가 크고 간선 수가 제한적이면 보통 인접 리스트가 메모리와 탐색 시간 면에서 유리하다.
DFS와 BFS
DFS는 한 경로를 끝까지 탐색한 뒤 돌아오고, BFS는 가까운 노드부터 같은 거리 순서로 탐색한다.
- DFS: 연결 요소, 사이클 확인, 경로 존재 여부, 백트래킹
- BFS: 간선 가중치가 같은 그래프의 최단 거리, 레벨별 탐색
- 공통 핵심: 이미 방문한 노드를 기록해 재방문을 막음
인접 리스트를 사용하면 두 탐색 모두 시간 복잡도는 `O(V + E)`다. 여기서 `V`는 노드 수, `E`는 간선 수다.
문제 조건별 알고리즘 선택
| 문제 조건 | 우선 고려할 방법 |
|---|---|
| 모든 연결 그룹 확인 | DFS, BFS |
| 가중치가 같고 최단 거리 | BFS |
| 양수 가중치의 최단 거리 | 다익스트라 |
| 작업 순서와 의존성 | 위상 정렬 |
| 모든 노드를 잇는 최소 비용 | 크루스칼, 프림 |
| 그룹 합치기와 연결 여부 | Union-Find |
자주 하는 실수
- 방문 배열을 누락해 같은 노드를 계속 방문하는 경우
- 무방향 간선을 한 방향으로만 저장하는 경우
- 방문 표시를 늦게 해 큐나 재귀 호출에 같은 노드가 여러 번 들어가는 경우
- BFS에서 큐에 넣을 때가 아니라 꺼낼 때 방문 처리해 거리가 중복 갱신되는 경우
- 재귀 DFS가 깊어질 때 언어별 재귀 깊이 제한을 고려하지 않는 경우