dfs 알고리즘 & 네트워크 C++

dfs = 깊이 우선 탐색

1. dfs 알고리즘이란?

: 그래프 전체를 탐색하는 방법 중 하나로, bfs와 달리 깊이 우선 탐색을 함.

• stack 또는 재귀를 사용
• 현재 정점에서 갈 수 있는 점들까지 깊게 탐색
• 장점 : 현재 노드 경로만 기억하면 됨으로, 저장공간 수요가 적고, 목표노드가 깊은 곳에 위치할 경우, 보다 빠르게 해를 구할 수 있음.
• 단점 : 해가 없는 경로에 깊히 빠질 수 있고, 얻어진 해가 최단 경로라는 보장이 없음.

2. dfs 구현

- stack으로 구현하기

• 절차
  a. 시작 노드를 방문 후 제일 밑까지 깊게 파고들어가면서 stack에 저장.
  => 파고 들어가는 기준을 두면 되는데, 보통 숫자 작은 노드 먼저 방문.
  b. 제일 깊이 내려왔으면, stack에서 pop 후, 부모 노드의 다른 자식이 있다면, 해당 노드를 쭉 타고 내려가면서 stack에 저장.
  c. 다른 자식이 없다면 한번 더 pop해서 부모 노드로 이동. b와 c를 계속 반복.
  d. stack에 모든 값이 소진될 때 까지 반복.

- 재귀로 구현하기

• 절차
  a. 시작 노드를 방문 후 방문처리.
  b. 인접한 노드 재귀함수 호출, 방문 처리.
  c. 방문한 노드인 경우 return. 아닌 경우 b를 반복.

3. 프로그래머스 네트워크 문제 (dfs)

• 재귀 사용

#include <string>
#include <vector>

using namespace std;

void dfs(int n, int size, vector<vector<int>> computers, int *visited)
{
    visited[n] = 1;
    for (int i = 0; i < size; i++)
    {
        if (computers[n][i] && !visited[i])
            dfs(i, size, computers, visited);
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    int *visited = new int[computers.size()]{};
    
    for (int i = 0; i < computers.size(); i++)
    {
         if (visited[i] == 0)
         {
             dfs(i, computers[i].size(), computers, visited);
             answer++;
         }
    }
    return answer;
}

• 참고
  • 동적할당
    • new int[원하는 size]로 생성
    • 뒤에 {}가 오면 0으로 초기화