[Programmers]#Level3_네트워크, DFS, 깊이 우선 탐색

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. 깊이 우선 탐색

 

[자료구조]#6_그래프

DFS(깊이 우선 탐색)은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. DFS는 출발 정점으로부터 더 이상 확장 불가능한 단말 노드까지 우선 탐색하는 방법입니다. 일반적으로, DFS는 재귀 호출 혹은 스택을 활용하여 구현합니다.

 

2. 모든 정점을 시작 정점으로 하여 DFS를 수행합니다!

 

1. 주어진 2차원 벡터(computers)를 그래프로 가정하고, 각 컴퓨터를 시작 정점으로 하는 DFS를 수행합니다.
2. 이때, DFS 수행 과정에서 각 컴퓨터의 방문여부를 체크해, 중복 방문을 방지해 줍니다.

 

---

 

#3. 코드

 

/*
    @문제 : 네트워크를 형성하는 경로의 개수
    @설명
            1. 각 정점에 대하여 깊이 우선 탐색을 수행합니다.
            2. 각 정점을 기준으로 깊이 우선 탐색을 수행하며 방문한 정점에 대하여 방문 여부를 체크합니다.
            2. 방문 여부가 참인 정점은 이후 탐색 작업에서 제외되며, 다른 네트워크를 찾아냅니다.
*/

#include <string>
#include <vector>

using namespace std;

int network;
vector<bool> visited;

void dfs(int cur, vector<vector<int>> &graph)
{
    visited[cur] = true;

    for (int i = 0; i < (int)graph.size(); ++i)
    {
        if (i == cur)
            continue;

        if (graph[cur][i] != 0 && !visited[i])
        {
            dfs(i, graph);
        }
    }
}

int solution(int n, vector<vector<int>> computers)
{

    visited.resize(n, false);

    for (int i = 0; i < n; ++i)
    {
        if (!visited[i])
        {
            dfs(i, computers);
            network++;
        }
    }

    return network;
}

 

---