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

문제 링크: programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

1. 주의할 점

- 이미 네트워크를 이룬 컴퓨터는 세지 않도록 한다

- 기본적인 BFS문제

 

2. 구현

- 전달받는 배열을 바탕으로, 1의 원소를 가지고 있다면(열!=행) V[] 벡터에 간선을 저장한다

- 0번부터 컴퓨터의 수-1 까지 For문을 돌리고 아직 네트워크를 형성하지 않은 컴퓨터라면(Check[] 값이 false) Queue에 넣고 해당 컴퓨터와 연결된 모든 컴퓨터들의 Check[]값을 True로 바꾼후 Answer++한다 (추가적인 네트워크 형성 했다는 의미)

 

#include <string>
#include <vector>
#include <vector>
#include <queue>
using namespace std;
bool check[200]={false,};
vector<int> v[200];
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    for(int i=0;i<computers.size();i++){
        for(int j=i+1;j<computers[i].size();j++){
            if(computers[i][j]==1){
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    for(int i=0;i<computers.size();i++){
        if(!check[i]){
            answer++;
            check[i]=true;
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int cidx = q.front();
                q.pop();
                for(int j=0;j<v[cidx].size();j++){
                    int next = v[cidx][j];
                    if(check[next]) continue;
                    check[next]=true;
                    q.push(next);
                }
            }
        }
    }
    return answer;
}