[C++] 프로그래머스 네트워크 풀이

갑자기 재밌어 보여서 푼 문제...

컴퓨터 간 연결된 네트워크의 갯수를 구하는 문제

 

---

문제의 조건

 

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

입력

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

 

출력

네트워크의 개수

 

 

풀이 과정

 

 기본적인 DFS/BFS 문제로 저는 DFS로 풀었습니다. 서로 연결되지 않은 컴퓨터도 있을 수 있기 때문에 모든 컴퓨터를 방문할 때까지 DFS로 컴퓨터들을 탐색하도록 했습니다. 주의사항이라면 입력으로 주어지는 computers 배열에서 다른 컴퓨터와 연결되어 있는지를 1로 표시하기 때문에 몇 번 컴퓨터와 연결되어 있는지 알려면 1이 있는 인덱스가 몇 번인지 알고 다음에 탐색할 노드를 지정해 주어야 합니다.(제가 처음에 이걸 생각 못 하고 대충 짰다가 틀렸거덩요...ㅎ...) 

 

1. 방문 표시용 배열을 만든다. 길이는 컴퓨터의 갯수만큼 정한다. 

 

2. DFS 함수를 만든다. 현재 방문중인 컴퓨터를 방문하지 않았다면 방문 표시를 하고 computers 배열에서 현재 컴퓨터 번호에 해당되는 인덱스를 탐색한다.

ex) 현재 0번 컴퓨터를 방문중이라면 computers[0] 번 인덱스에 있는 원소들을 탐색한다. 

 원소들 중 1인 인덱스가 있다면... 그리고 그 인덱스 번호를 방문하지 않았으면 방문 표시를 하고 DFS 함수를 재귀호출해서 또 탐색한다. 

 

3. solution 함수에서 DFS 함수가 호출될 때마다 정답 카운트를 증가시킨다. 

 

 

코드

 

#include <string>
#include <vector>

using namespace std;

vector<bool> visited; //방문 표시용 배열 
void dfs(vector<vector<int>>& computers, int start)
{
    //현재 노드가 방문표시 되어 있지 않으면 표시 
    if (!visited[start])
        visited[start] = true;

    for (int i = 0; computers[start].size() > i; i++)
    {
        //i번째 인덱스(컴퓨터)를 방문하지 않았고 1(연결됨)이라면 방문표시 후 dfs 재귀호출 
        if (!visited[i] && 1 == computers[start][i])
        {
            visited[i] = true;
            dfs(computers, i);
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    visited.assign(n, false);

    int answer = 0;
    for (int i = 0; n > i; i++)
    {
        if (!visited[i])
        {
            //dfs 호출이 끝날 때마다 정답 카운트 증가 
            dfs(computers, i);
            answer++;
        }
    }

    return answer;
}