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

 

 

문제

문제 설명

 

 

[문제 요약]

​

컴퓨터와 컴퓨터가 연결되어 있으면 하나의 네트워크로 본다. 만약 A와 B컴퓨터 B와 C컴퓨터가 연결되어있다면, 하나의 네트워크로 간주한다.

컴퓨터간의 연결이 2차원 vector로 주어지면 컴퓨터들 간의 총 네트워크의 수는 얼마인지 return 하면 되는 문제다.

 

 

풀이

 

 

컴퓨터의 개수가 최대 200개로 크지 않았기 때문에 DFS로 쉽게 풀 수 있다는 생각이 들었다.

 

그래서 이미 네트워크로 체크했는지 검사하는 isNet이라는 1차원 vector를 이용해 DFS로 문제를 풀었다.

 

하나의 컴퓨터와 연결된 컴퓨터는 이미 연결된 네트워크인지 체크를 했다고 처리를 하는 것이다.

​

[아이디어 정리]

1. 컴퓨터의 개수만큼 for문을 돌려 DFS로 네트워크의 수를 구한다.​
2. 만약 이전에 방문한 컴퓨터라면 네트워크가 연결된 것이므로, 넘어간다.​
3. 총 네트워크 수를 return하면 된다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    vector<bool> isNet(n,false);
    vector<int> stack;
    int nowCom;
    for (int i=0; i<n; i++)
    {
        if (!isNet[i])
        {
            answer+=1;
            stack.push_back(i);
            isNet[i]=true;
            while (stack.size()>0)
            {
                nowCom=stack.back();
                stack.pop_back();
                for (int j=0; j<n; j++)
                {
                    if (!isNet[j] && computers[nowCom][j]==1)
                    {
                        stack.push_back(j);
                        isNet[j]=true;
                    }
                }
            }
        }
    }    
    return answer;
}

 

---

 

 

다른 방법을 생각해보려 했는데, 제한사항이 작고 간단한 DFS문제라 빠르게 풀었다.

 

프로그래머스