[Lv 3] 네트워크

https://school.programmers.co.kr/learn/courses/30/lessons/43162#

프로그래머스

 

dfs를 사용해 해결하였다.

1을 만나면 dfs를 진행한다.

이때 1에서 2가 연결되어 있다면 2의 입장에서 연결된 다른 컴퓨터를 찾는다. 

찾을 수 있다면 방문 표시를 하고 다 찾았다면 네트워크 수를 1 증가시킨다. 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;
bool visited[200][200];

void dfs(int y, int x, vector<vector<int>> computers){
    queue<pair<int,int>> q;
    q.push({y,x});
    visited[y][x] = true;
    while(!q.empty()){
        int qy = q.front().first;
        int qx = q.front().second;
        q.pop();
        
        for(int i = 0;i<computers[qx].size();i++){
            if(computers[qx][i] == 1 && !visited[qx][i]){
                q.push({qx,i});
                visited[qx][i] = true;
            }
        }
    }
}

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i = 0;i<computers.size();i++){
        for(int j = 0;j<computers[i].size();j++){
            if(computers[i][j] == 1 && !visited[i][j]){
                dfs(i,j, computers);
                answer++;
            }
        }
    }
    return answer;
}