프로그래머스 : DFS/BFS - 네트워크

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

프로그래머스

---

문제 자체는 그냥 평범하게 그래프를 탐색하는 문제였다!

 

다양한 풀이방법이 있는것 같지만, 나는 BFS로 풀었다 (맞겠지?)

 

n개의 컴퓨터 중, seed한개를 잡아서, 네트워크를 타고타고 가면서 탐색한다 (BFS)

-> 한번의 탐색이 마무리되면 (큐가 비었으면) 네트워크 한개를 찾은것!

또 남은 컴퓨터중 (아직 가보지 않은곳) 하나를 seed삼아서 BFS탐색을 반복한다

모든 컴퓨터를 탐색하면, 종료된다.

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

using namespace std;

int solution(int n, vector<vector<int> > computers) {
    int answer = 0;
    
    vector<int> computerss(n, 1);
    bool flag = true;
    
    int seed = 0;
    
    while(flag){
        if(find(computerss.begin(), computerss.end(), 1) == computerss.end()){
            break;
        }
        for(int i = 0; i<n; i++){
            if(computerss[i] == 1){
                seed = i;
                break;
            }
        }
        queue<int> que;
        que.push(seed);
        
        while(!que.empty()){
            int computer = que.front();
            que.pop();
            computerss[computer] = 0;
            for(int i = 0; i<n; i++){
                if(i != computer){
                    if(computers[computer][i] == 1){
                        que.push(i);
                        computers[computer][i] = 0;
                    }
                }
            }
        }
        answer++;
        
        
    }
    
    return answer;
}

---

조금 더 간결한 풀이가 있을것같긴한데,, 모르겠다!