🌞문제

🌞접근법

조건1. 컴퓨터의 개수는 n
조건2. 연결에 대한 정보가 담긴 배열 computers / computers[i][j] = 1 일때, i번째 컴퓨터와 j번째 컴퓨터는 연결 돼있다는 뜻이다.
조건3. n은 1~200의 자연수
조건4. 각 컴퓨는 0~n-1인 정수로 표현
조건5. computer[i][i] = 무조건 1이다.

결과값 : 네트워크의 개수는 몇 개?

예시로 주어진 입출력 예제를 먼저 살펴보자.
n=3 이고, computers를 살펴보면
0 - 1 2
0 - 1 2
0 1 2
0과 1은 연결이 돼 있지만, 2는 연결이 돼 있지 않는다.
즉 이경우 두개의 네트워크가 있다고 한다.

이 경우 dfs를 하면 좋을 것 같다고 생각이 든다.
일단 for문을 n번만큼을 실행한다. - 이 for문은 computers의 모든 요소를 돌게 하는 for문
그리고 for문에 들어가서는 미리 만들어둔 visit배열을 확인하여 이미 탐색을 한 항목인지를 확인한다.
만약에 탐색을 하지 않은 항목이다. 이 경우에는 큐에 computers의 j에 해당하는 값을 큐에 추가한다.
그리고 큐가 비어질 때 까지 위의 행동을 반복한다.
그렇게 해서 큐가 비어지면 for문을 다시 이어서 하게 된다.
visit을 확인해서 그 값을 방문한 적이 없다면 네트워크 값을 하나 늘려주고, 위의 일을 다시 반복한다.

🌞답

#include <string>
#include <vector>
#include <queue>

using namespace std;

int visit[201];
int cnt = 0;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    queue<int> q;
    for(int i=0;i<n;i++)
    {
        if(visit[i] == 0)
        {
            cnt++;
            visit[i] = 1;
            for(int j=0;j<n;j++)
            {
                if(computers[i][j] == 1 && visit[j] == 0){
                    q.push(j);
                    visit[j] = 1;
                }
            }
            while(!q.empty())
            {
                int x = q.front();
                q.pop();
                for(int k=0;k<n;k++)
                {
                    if(computers[x][k] == 1 && visit[k] == 0)
                    {
                        q.push(k);
                        visit[k] = 1;
                    }
                }
            }
        }
    }
    
    answer = cnt;
    
    return answer;
}