소프트웨어 개발자로 취업하기 위해서는 알고리즘 시험이 중요합니다. 특히 DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색의 기본 개념으로, 많은 문제에서 활용됩니다. 이 글에서는 DFS와 BFS 알고리즘을 사용한 문제를 소개하고, 문제 해결 과정을 자세히 설명하겠습니다.
문제 설명
가장 먼저, 다음과 같은 그래프가 있다고 가정해봅시다. 이 그래프는 정점(Vertex)과 간선(Edge)으로 구성되어 있습니다. 다음 그래프를 탐색하여 특정 정점을 찾는 문제를 해결해보겠습니다.
문제
그래프가 주어질 때, 주어진 시작 정점에서 특정 정점을 찾기 위한 DFS와 BFS 알고리즘을 구현하시오.
입력
- 정점의 수:
n(2 ≤ n ≤ 100) - 간선의 수:
m(1 ≤ m ≤ 300) - 간선의 목록: 각 간선은 두 정점으로 구성됨 (u, v)
- 시작 정점:
start - 찾고자 하는 정점:
target
출력
시작 정점에서부터 target 정점까지 도달할 수 있으면 true, 없으면 false를 출력합니다.
문제 풀이
이번 문제는 DFS와 BFS 알고리즘을 통해 해결할 수 있습니다. 두 방법 모두 그래프 탐색을 위해 널리 사용되는 기법입니다. 두 알고리즘의 동작 원리를 먼저 살펴보겠습니다.
DFS(Depth-First Search)
DFS는 깊이 우선 탐색으로, 한 노드를 깊게 탐색한 뒤 더 이상 탐색할 노드가 없으면 뒤로 돌아와 다른 노드를 탐색하는 방식입니다. 스택을 사용하여 구현할 수 있습니다.
BFS(Breadth-First Search)
BFS는 너비 우선 탐색으로, 한 노드의 모든 이웃 노드를 탐색한 뒤, 다음 이웃 노드를 탐색하는 방식입니다. Queue 자료구조를 사용하여 구현할 수 있습니다.
구현
이제 C#으로 DFS와 BFS 알고리즘을 구현해보겠습니다.
1. 그래프 표현
그래프는 인접 리스트 형태로 표현할 수 있습니다. 각 노드에 대해 연결된 노드를 리스트 형태로 저장합니다.
public class Graph
{
private int vertices; // 정점의 수
private List[] adjList; // 인접 리스트
public Graph(int n)
{
this.vertices = n;
adjList = new List[n];
for (int i = 0; i < n; i++)
{
adjList[i] = new List();
}
}
// 간선 추가 메소드
public void AddEdge(int u, int v)
{
adjList[u].Add(v);
adjList[v].Add(u); // 무향 그래프
}
public List GetNeighbors(int vertex)
{
return adjList[vertex];
}
}
2. DFS 구현
DFS는 다음과 같이 재귀적인 방법으로 구현할 수 있습니다.
public class DFS
{
private bool[] visited;
private Graph graph;
public DFS(Graph g)
{
this.graph = g;
this.visited = new bool[g.vertices];
}
public bool Search(int start, int target)
{
// 현재 노드를 방문 처리
if (start == target) return true;
visited[start] = true;
foreach (int neighbor in graph.GetNeighbors(start))
{
if (!visited[neighbor] && Search(neighbor, target))
{
return true; // 타겟 발견
}
}
return false; // 타겟 발견하지 못함
}
}
3. BFS 구현
BFS는 Queue를 사용하여 다음 노드를 탐색하는 방식으로 구현합니다.
using System.Collections.Generic;
public class BFS
{
private bool[] visited;
private Graph graph;
public BFS(Graph g)
{
this.graph = g;
this.visited = new bool[g.vertices];
}
public bool Search(int start, int target)
{
Queue queue = new Queue();
queue.Enqueue(start);
visited[start] = true;
while (queue.Count > 0)
{
int current = queue.Dequeue();
if (current == target) return true;
foreach (int neighbor in graph.GetNeighbors(current))
{
if (!visited[neighbor])
{
queue.Enqueue(neighbor);
visited[neighbor] = true;
}
}
}
return false; // 타겟 발견하지 못함
}
}
테스트 케이스
이제 구현한 알고리즘을 테스트하기 위해, 간단한 그래프를 만들어 보겠습니다.
public class MainClass
{
public static void Main(string[] args)
{
Graph graph = new Graph(5);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(1, 4);
graph.AddEdge(2, 4);
DFS dfs = new DFS(graph);
BFS bfs = new BFS(graph);
Console.WriteLine("DFS: " + dfs.Search(0, 4)); // true
Console.WriteLine("BFS: " + bfs.Search(0, 4)); // true
Console.WriteLine("DFS (No path): " + dfs.Search(0, 5)); // false
Console.WriteLine("BFS (No path): " + bfs.Search(0, 5)); // false
}
}
종합 정리
이번 강좌에서는 DFS와 BFS 알고리즘을 통해 그래프 탐색 문제를 해결하는 방법을 살펴보았습니다. 각각의 탐색 방법은 장점과 단점이 있으며, 문제의 성격에 따라 적절한 방법을 선택해야 합니다. DFS는 메모리 사용이 적고, 깊이 있는 문제를 해결할 때 유리하지만 경로를 찾는 데 시간이 더 걸릴 수 있습니다. 반면, BFS는 최단 경로를 찾는 데 유리하지만, 메모리 사용량이 많을 수 있습니다.
이 기사를 통해 DFS와 BFS를 이해하고, 다양한 코딩 테스트 문제에 대응할 수 있는 역량을 기르기를 바랍니다.
참고 자료
- Geeks for Geeks
- LeetCode
- 알고리즘 관련 서적
결론
코딩테스트는 개발자로서의 기본 역량을 평가하는 중요한 과정입니다. DFS와 BFS 알고리즘은 그래프 탐색의 기초적인 방법으로, 기본기를 다지는 데 큰 도움이 됩니다. 다양한 알고리즘과 자료구조를 익히고, 연습을 통해 실력을 키워나가길 바랍니다.