2606号-ウイルス(c++)

🗒 2606題

📌 幅優先ナビゲーションを使用する問題

    1️⃣ 너비 우선 탐색이 뭐예요..? 
    A. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
    
    2️⃣ 시작 정점에서 가까운 정점을 먼저 탐색 -> 먼 정점은 나중에 탐색하는 게 너비 우선 탐색
    
    3️⃣ 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다
    
    4️⃣ BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다
    -> 선입선출(FIFO) 원칙으로 탐색
    
    5️⃣ 방문하는 방법
    	1. a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
	2. 큐에 방문된 노드를 삽입(enqueue)한다.
	3. 초기 상태의 큐에는 시작 노드만이 저장
	4. 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
	5. 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
	6. 큐에서 꺼낸 노드를 방문한다.
	7. 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
	8. 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
	9. 큐에 방문된 노드를 삽입(enqueue)한다.
	10. 큐가 소진될 때까지 계속한다(empty())
	
    6️⃣ 재귀함수로 구현 불가!!!⚡️⚡️

看板6号

#include <iostream>
#include <vector>
#include <queue> // queue를 사용하는 bfs
using namespace std;

int main() {
    vector<int> nodes[101];
    queue<int> q;
    bool entered[101];
    int comNum, netNum, count = 0;
    
    cin >> comNum >> netNum;
    
    for (int i = 0; i < netNum; i++) {
        int n, m;
        
        cin >> n >> m;
        nodes[n].push_back(m); //vector로 만든 node에 넣기
        nodes[m].push_back(n);
    }
    entered[1] = true;
    q.push(1);
    
    // queue가 빌 때까지
    while (!q.empty()) {
        int n = q.front();
        q.pop();
        
        for (int i = 0; i < nodes[n].size(); i++) {
            int j = nodes[n][i];
            
            if(entered[j] == false) {
                entered[j] = true;
                q.push(j);
            }
        }
    }
    
    for (int i = 1; i <= comNum; i++) {
        if (entered[i] == true) // 1번과 연결되어 바이러스 들어간 노드만 카운트
            count++;
    }
    
    cout << count - 1 << endl;
}