[Algorithm] DFS, BFS, Greedy, MST(최소 신장 트리)

그래프 탐색의 대표 알고리즘인 DFS, BFS, 탐욕 알고리즘인 Greedy, 그리고 최소 신장 트리(MST) 에 대해 공부했다. 각 알고리즘의 특징과 언제 사용하는지, 구현 방법을 중심으로 정리하였다.

---

1. DFS / BFS 문제 유형

그래프 탐색 문제는 크게 다음과 같은 유형으로 자주 출제된다.

1) 경로 탐색 유형

• 시작점에서 도착점까지 이동 가능한지 확인
• 특정 경로를 찾는 문제

2) 미로 탐색 유형

• 최단 거리
• 이동 가능한 칸 탐색

3) 조합 탐색 유형

• 모든 경우의 수 탐색
• 백트래킹과 함께 자주 사용

---

DFS와 BFS 구현 방법

DFS

• Stack
• 또는 재귀 함수를 이용하여 구현

dfs(start);

---

BFS

• Queue
• LinkedList 또는 ArrayDeque 사용

Queue<Integer> q = new LinkedList<>();

---

2. DFS(Depth First Search)

DFS란?

DFS는 한 방향으로 최대한 깊게 탐색한 뒤 더 이상 갈 곳이 없으면 이전 노드로 돌아와 다른 경로를 탐색하는 방식이다.

대표적으로

• 그래프 탐색
• 백트래킹
• 연결 요소 찾기

등에서 많이 사용된다.

---

DFS 특징

• Stack(또는 재귀) 사용
• LIFO(Last In First Out)
• 방문 배열(visited) 필요
• 한 경로를 끝까지 탐색

---

DFS 탐색 과정

1. 시작 노드를 방문한다.
2. 방문하지 않은 인접 노드가 있으면 계속 이동한다.
3. 더 이상 이동할 수 없으면 이전 노드로 되돌아간다.
4. 모든 노드를 방문할 때까지 반복한다.

---

DFS 기본 코드

void dfs(int node){

    visited[node] = true;

    for(int next : graph[node]){

        if(!visited[next]){
            dfs(next);
        }

    }

}

---

DFS 시간 복잡도

그래프를 인접 리스트로 표현한 경우

O(V + E)

• V : 정점(Vertex)
• E : 간선(Edge)

---

3. BFS(Breadth First Search)

BFS란?

BFS는 시작점에서 가까운 노드부터 차례대로 탐색하는 알고리즘이다.

즉,

거리 1

↓

거리 2

↓

거리 3

순으로 탐색한다.

---

BFS 특징

• Queue 사용
• FIFO(First In First Out)
• 방문 배열 필요
• 최단 거리 문제에서 자주 사용

---

BFS 탐색 과정

1. 시작 노드를 Queue에 삽입한다.
2. Queue에서 하나를 꺼낸다.
3. 인접 노드를 모두 Queue에 넣는다.
4. Queue가 빌 때까지 반복한다.

---

BFS 기본 코드

Queue<Integer> q = new LinkedList<>();

q.offer(start);
visited[start] = true;

while(!q.isEmpty()){

    int cur = q.poll();

    for(int next : graph[cur]){

        if(!visited[next]){

            visited[next] = true;
            q.offer(next);

        }

    }

}

---

DFS와 BFS 비교

DFSBFS

Stack(재귀)	Queue
깊게 탐색	가까운 곳부터 탐색
백트래킹과 함께 사용	최단 거리 문제에 적합
구현이 비교적 간단	레벨 탐색 가능

---

4. Greedy(탐욕 알고리즘)

Greedy란?

Greedy 알고리즘은 매 순간 가장 최선이라고 생각되는 선택을 하는 알고리즘이다.

현재의 최적 선택이 전체 최적해로 이어지는 문제에서 사용할 수 있다.

---

Greedy 특징

1. 현재 가장 좋은 선택을 한다.
2. 이전 선택을 다시 변경하지 않는다.
3. 항상 최적해를 보장하는 것은 아니다.

---

대표 문제

• 동전 거스름돈
• 회의실 배정
• 활동 선택 문제
• 최소 비용 문제

---

Greedy를 사용할 수 있는 조건

Greedy가 적용되려면 일반적으로 다음 조건을 만족해야 한다.

1. 탐욕 선택 속성(Greedy Choice Property)

현재의 최선의 선택이 전체 최적해로 이어진다.

---

2. 최적 부분 구조(Optimal Substructure)

부분 문제의 최적해가 전체 문제의 최적해를 구성한다.

---

5. MST(Minimum Spanning Tree)

최소 신장 트리란?

최소 신장 트리는 모든 정점을 연결하면서 사이클이 발생하지 않도록 하는 트리 중 간선의 가중치 합이 최소인 트리이다.

즉,

• 모든 정점 연결
• 사이클 없음
• 간선 가중치 최소

를 만족해야 한다.

---

MST 특징

정점이 N개라면

간선 개수 = N - 1

이다.

---

대표 알고리즘

Kruskal Algorithm

간선을 기준으로 선택한다.

순서

1. 간선을 가중치 기준 오름차순 정렬
2. 가장 작은 간선부터 선택
3. 사이클이 발생하면 선택하지 않는다.
4. 모든 정점이 연결될 때까지 반복

사이클 판별에는 Union-Find를 사용한다.

---

Prim Algorithm

정점을 기준으로 선택한다.

순서

1. 임의의 정점 선택
2. 연결 가능한 간선 중 가장 작은 간선을 선택
3. 새로운 정점을 트리에 포함
4. 모든 정점이 연결될 때까지 반복

---

Kruskal에서 Union-Find 사용 이유

간선을 선택할 때

A ----- B

↓

이미 같은 집합?

YES

↓

사이클 발생

↓

선택하지 않음

이 과정을 매우 빠르게 수행하기 위해 Union-Find를 사용한다.

---

 

DFS는 깊이 우선 탐색으로 Stack(또는 재귀)을 이용해 구현하며, 백트래킹과 함께 자주 사용된다는 점을 다시 확인했다. 반면 BFS는 Queue를 사용하여 가까운 노드부터 탐색하기 때문에 최단 거리 문제에서 매우 효과적이라는 것.

 

Greedy 알고리즘은 매 순간 최선의 선택을 하는 방식이지만, 항상 정답을 보장하는 것은 아니므로 문제의 조건을 먼저 확인해야 한다는 점.

 

마지막으로 MST는 모든 정점을 최소 비용으로 연결하는 알고리즘이며, Kruskal에서는 Union-Find를 활용해 사이클을 판별하고, Prim은 정점을 확장해 나간다는 차이점도 정리할 수 있었다.