[Algorithm] DFS (깊이 우선 탐색) 알고리즘

DFS(Depth-First Search)는 그래프나 트리와 같은 자료구조를 탐색하는 데 사용되는 알고리즘이다. 한 노드에서 시작하여 가능한 한 깊이 탐색한 후, 더 이상 탐색할 경로가 없을 때 되돌아와(백트래킹) 다른 경로를 탐색하는 방식이다.

---

알고리즘 원리

DFS는 재귀 함수 또는 스택(Stack)을 이용하여 구현할 수 있다.

1. 시작 노드를 선택하고 방문한다.
2. 방문한 노드와 연결된 이웃 노드 중 아직 방문하지 않은 노드를 선택하여 깊이 우선으로 탐색한다.
3. 더 이상 갈 곳이 없을 때, 이전 노드로 되돌아와(백트래킹) 다른 경로를 탐색한다.
4. 모든 노드를 방문할 때까지 이 과정을 반복한다.
   DFS를 사용하는 대표적인 유형으로는 경로탐색(최단거리, 시간), 네트워크 유형(연결), 조합 유형(모든 조합 만들기)이 있다.
   
   

---

코드 구현

이 코드는 프로그래머스 사이트의 네트워크 문제를 해결하기 위한 DFS 구현 예시다.

1. 재귀 함수

using System;

public class Solution
{
    public int solution(int n, int[,] computers)
    {
        bool[] visited = new bool[n];
        int networkCount = 0;
        
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
            {
                networkCount++;
                DFS(i, n, computers, visited);
            }
        }
        
        return networkCount;
    }
    
    void DFS(int node, int n, int[,] computers, bool[] visited)
    {
        visited[node] = true;
        
        for (int i = 0; i < n; i++)
        {
            if (computers[node, i] == 1 && !visited[i])
            {
                DFS(i, n, computers, visited);
            }
        }
    }
}

2. 반복문 (Stack 자료구조)

using System;
using System.Collections.Generic;

public class Solution
{
    public int solution(int n, int[,] computers)
    {
        bool[] visited = new bool[n];
        int networkCount = 0;
        
        for (int i = 0; i < n; i++)
        {
            if (!visited[i])
            {
                networkCount++;
                visited[i] = true;
                Stack<int> stack = new Stack<int>();
                stack.Push(i);
                
                while (stack.Count > 0)
                {
                    int node = stack.Pop();
                    
                    for (int j = 0; j < n; j++)
                    {
                        if (computers[node, j] == 1 && !visited[j])
                        {
                            stack.Push(j);
                            visited[j] = true;
                        }
                    }
                }
            }
        }
        
        return networkCount;
    }
}