[ 프로그래머스 네트워크 (Lv3) ] (C++)

프로그래머스의 네트워크(Lv3) 문제이다.

[ 문제풀이 ]

컴퓨터와 컴퓨터들 간의 연결 관계가 주어질 때, 네트워크의 갯수를 구하는 문제이다.

본인은 이 문제를 깊이우선탐색(DFS)을 통해서 접근해 보았다.

DFS를 통해서, 하나의 컴퓨터로부터 연결되어 있는 컴퓨터로 모두 방문하면서 방문 체크를 해준다.

이 과정을 "아직 방문하지 않은 컴퓨터"에 대해서 반복한다면, DFS함수가 호출되는 횟수가 네트워크의 갯수가 된다.

.

위와 같은 예시를 한번 보자.

먼저, "방문하지 않은 컴퓨터"에 대해서 DFS함수를 호출하는 과정을 보자.

가장 먼저 '1'번 컴퓨터는 아직 방문하지 않았으므로(초기의 방문상태는 모두 방문하지 않은 상태임.) 1번컴퓨터로 DFS를 호출해보자. DFS함수 안에서는 연결되어 있는 모든 컴퓨터로 방문체크를 하면서 진행될 것이다.

그렇게 되면, 1번 컴퓨터에서 2번 컴퓨터, 2번컴퓨터에서 3번컴퓨터로, 3번컴퓨터에서 4번 컴퓨터로 탐색을 진행하게 될 것이다.

그 다음 컴퓨터도 마찬가지로 진행해보자. 2번 컴퓨터를 보니, 1번컴퓨터에서 탐색을 하는 과정에서 이미 방문한 컴퓨터 이기 때문에 넘어가자. 3번 컴퓨터도, 4번컴퓨터도 마찬가지일 것이다.

즉 ! 우리는 위와 같은 경우에서는 DFS 함수가 1번만 호출된 것을 알 수 있다. 즉 ! 위의 경우에는 존재하는 네트워크의 갯수가 1개

라는 것이다.

.

이 경우를 한번 보자. 마찬가지로 1번 컴퓨터 부터 탐색을 진행한다면, 1번 컴퓨터에서 2번컴퓨터 까지 가고 더 이상 탐색할 수 있는 컴퓨터가 없으므로 탐색이 중단될 것이다.

이 후, 2번 컴퓨터는 이미 1번 컴퓨터에서 탐색할 때 방문한 컴퓨터가 되고, 3번 컴퓨터에서 다시 DFS 함수가 호출될 것이다.

3번 컴퓨터에서는 4번 컴퓨터까지 가게 될 것이고 탐색이 중단될 것이다.

즉 ! 이 경우를 보게되면, DFS함수가 총 2번 호출된 것을 알 수 있다. 즉 ! 위의 경우에는 존재하는 네트워크의 갯수가 2개라는 것이다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
bool Visit[210];
 
void DFS(int n, int Cur, vector<vector<int>> V)
{
    for (int i = 0; i < n; i++)
    {
        if (V[Cur][i] == 1 && Visit[i] == false)
        {
            Visit[i] = true;
            DFS(n, i, V);
        }
    }
}
 
int solution(int n, vector<vector<int>> computers) 
{
    int answer = 0;
    for (int i = 0; i < n; i++) Visit[i] = false;
    for (int i = 0; i < n; i++)
    {
        if (Visit[i] == false)
        {
            Visit[i] = true;
            DFS(n, i, computers);
            answer++;
        }
    }
    return answer;
}