백준 2606번 바이러스 (bfs/플로이드-와샬 알고리즘)

며칠만에 bfs 다시 풀려고하니까 어떻게 해야되는지 까먹어서 조금 고민했던 문제.. 틀린 원인 까지 분석해보겠다

우선 문제 자체는 기본적인 bfs문제이다.

비 방향 그래프가 주어지고 1번컴퓨터와 연결된 모든 컴퓨터의 개수를 세는 문제이다.(1번컴퓨터 제외)

문제를 보자마자 dfs 혹은 bfs를 적용하면 쉽게 풀릴것 같았고, 그중에서도 bfs를 쓰는게 더 빨리 답을 찾을수 있을것 같았다.

대충 알고리즘 동작 방식은 문제에 주어진 입력을 W[i][j]의 인접행렬로 바꾸고

그리고 나서 bfs를 시작하는데 1번컴퓨터 부터 bfs를 시작하게끔 설계했다.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <deque>
using namespace std;
int w[101][101];
bool check[101];
int n,m;
deque<int> deq;
 
int bfs()
{
    int count=-1; //count는 감염된 컴퓨터의 개수인데 1번컴퓨터는 포함이 안되서 -1부터 시작함.
    while(deq.size() != 0)
    {
        //노드 방문
        int current = deq.front();
        
        deq.pop_front();
        count++;
        //자식 노드 큐에 넣기 (다음 방문할곳)
        for(int j=1; j<=n; j++)
        {
            if(w[current][j] != 0 && check[j] == 0)
            {
                check[j] = 1;
                deq.push_back(j);
            }
        }
        
    }
    return count;
}
 
 
 
int main()
{
    cin >>n>>m;
    
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        w[x][y] = 1;
        w[y][x] = 1;
    }
  
    deq.push_back(1);
    check[1]=1;
    
    cout<<bfs()<<endl;
    
    return 0;
}

//자식 노드 큐에 넣기 (다음 방문할곳)

        for(int j=1; j<=n; j++)

        {

            if(w[current][j] != 0 && check[j] == 0)

            {

                check[j] = 1;

                deq.push_back(j);

            }

        }

이 부분 빼고 나머지는 이해가 될거라고 생각한다.

current란 bfs 트리에서 현재 위치(몇번 컴퓨터인가)에 대한 값이다.

문제 예시에 나온 그림을 봤을때 

bfs도중 현재 2번 컴퓨터에 와있다고 생각을 해보자.

그럼 2번 컴퓨터의 자식노드로 들어가야 할 것은 3번 컴퓨터뿐이다.

if(w[current][j] != 0 && check[j] == 0)

이 조건문은 현재 컴퓨터 (2번) 에서 연결된것 중에 => w[current][j] != 0

아직 방문하지 않은것 => check[j] == 0

을 자식 노드로 큐에 넣는다.

즉 3번만 들어가게끔 조건을 걸어 놓았다.

여기서 처음에 내가 2번이나 틀린 이유를 설명하겠다.

처음에 나는 이 그래프가 비 방향 그래프 인점을 빼먹고 알고리즘을 짰다 그래서 예시대로는 답이 잘나왔지만 16%에서 틀려버렸다.

w[x][y] = 1; w[y][x] = 1; 이 부분을 그냥 w[x][y]=1;이라고만 했으니

문제가 예시대로 나오면 상관이 없지만 거꾸로 6번부터 입력이 들어오면 제대로 값을 계산하지 못했기 때문에 틀렸다.

두번째 틀린 이유는

내가 노드를 방문했다고 체크한것을 자식 노드를 큐에 넣기전에 체크한게 아니라

현재 노드를 방문한(21번줄) 직후 그 노드를 방문했다고 체크했기 때문이다

이렇게 될경우 2번에서 자식노드를 큐에 넣을때 5번이 아직 방문이 안된상태라고 인식을 하기때문에 

2번의 자식에 5번이 들어가게되는 불상사가 발생한다.

그렇기 때문에 현재 노드를 방문했을때 check배열을 1로 업데이트 할게 아니라 자식을 큐에 넣을때 

1로 업데이트를 해주어야 했다.