[백준 2606번] 바이러스 |그래프의 탐색법|

http://www.acmicpc.net/problem/2606

2606번: 바이러스

___________________________________________________

입력

1.컴퓨터의 수가 주어진다. 

num (1 ≤ num ≤100)

2.네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수

간선의 개수 edge(1 ≤ edge ≤ 10,000)

3. 간선관계

___________________________________________________

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 

첫째 줄에 출력한다.

사이즈 출력

___________________________________________________

필요한 자료구조들

벡터

그래프를 만들기 위해서

방문배열을 만들기 위해서

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법

큐

BFS를 만들기 위해서.

___________________________________________________

for문의 다양한 사용법

1.for(int nxt :G[node] )

https://boycoding.tistory.com/210

C++ 07.18 - 범위 기반 for 문 (range-based for statement)

2.이터레이터

https://hyeonstorage.tistory.com/318

[STL] 반복자 iterator 개념 및 예제

___________________________________________________

생각방법.

A.그래프 만들기

양방향 간선이므로

1->2 있으면 2->1도 있어야한다.

사실.. 정대각 행렬들을 기준으로 선대칭이다.

B.탐색방법 설계

___________________________________________

큐의 push pop을 이용해서 탐색한다.

#while : queue가 빌때까지

#for : next 주변 노드 고르기

#is visit? : yes or no

visit할때마다 바이러스 걸린 컴퓨터의 대수 Size++

자기자신은 제외!

1.BFS(시작정점);

2.queue push(시작정점)

3.while(queue가 아직 뭔가 채워져있나?)

{

-채워쳐 있는 원소 front값 (정점번호)하나 가져오고

(정점번호를 popnode라고 하면)

그다음 pop한다.

-for문으로 popnode 의 주변노드 next_node를 고른다.

{

고른 next_node가 이미 방문되었나?

no : queue push(next_node)

visit[next_node] = true;

Size++

yes : 이면 다른정점을 찾아 for문 continue;

}

}

https://colorscripter.com/

_________________________________________

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
/////////////////////////////////
int num; //컴퓨터 대수
int edge;
int INFECT_SIZE;
/////////////////////////////////
vector<int> G[101];
queue<int> q;
bool visit[101];
/////////////////////////////////
 
 
int main()
{
    cin >> num >> edge;
    int S = 1;
    S--;
    for (int i = 0; i < edge; i++)
    {
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
 
    visit[S] = true;
    q.push(S);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
 
        for (int nxt : G[cur])
        {
            if (!visit[nxt])
            {
                q.push(nxt);
                visit[nxt] = true;
                INFECT_SIZE++;
            }
        }
    }
 
    cout << INFECT_SIZE << '\n';
}