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

✅ LV. 3
🔖 BFS

✏️ 1차 솔루션

• 큐: 검사할 컴퓨터들 관리
• vector v : 검사한 컴퓨터 표시

1. 초기화: 첫번째 컴퓨터인 0 을 큐에 넣음
2. 큐가 비어있을 경우
   1) 네트워크 개수 추가
   2) for 문으로 방문하지 않은 컴퓨터 번호 찾아 큐에 push
   3) 모든 컴퓨터를 방문했을 경우, 네트워크 개수 return
3. 큐에 원소가 있을 경우
   1) front 원소를 현재 인덱스로 설정하고 pop
   2) for 문으로 한번더 검사하지 않았던 컴퓨터이면서 현재 컴퓨터와 연결되어 있는 컴퓨터 인덱스 찾아서 큐에 push

🚨 1차 trouble

1. 큐가 비었을 때 count 하도록 구현한 answer (네트워크 개수)이 제대로 책정되지 않음
2. 이미 방문한 컴퓨터인지 검사할 때 for 문으로 탐색하는 것이 비효율적
3. 큐가 비었을 때까지 탐색을 하기에는 전체 컴퓨터를 검사하기는 해야하기 때문에 비효율적이고 for 문으로 하자니 이중 for 문을 남발하고 변수도 남발하게 됨

✏️ 최종 솔루션

큐가 비었을 경우, 아직 방문하지 않았던 컴퓨터를 찾기 위해 for 문을 사용하는 것이 아니라 find 함수를 사용해 vector v 에서 0 인덱스를 찾아 해당 인덱스를 큐에 push 해서 모든 컴퓨터를 탐색할 때까지 반복
이 방법을 통해 for 문을 남발하지 않고 코드도 간결하게 구현할 수 있었음

🔗 [C++] find 함수

✏️ 최종 코드

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

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    queue<int> q;
    vector<int> v(n,0);
    q.push(0);
    
    while(1) {
        if(q.empty()) {
            answer++;
            auto idx=find(v.begin(),v.end(),0);
                
            if(idx==v.end()) return answer;
            
            q.push(idx-v.begin());

        }
        
        int cur=q.front();
        q.pop();
        v[cur]=1;
        
        for(int i=0;i<n;i++) {
            if(v[i]==0&&computers[cur][i]==1) q.push(i);
        }
    }

    return answer;
}