[백준] 2606번 바이러스 (C++) - DFS, BFS

문제

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

2606번: 바이러스

코드

dfs

#include <iostream>

using namespace std;

int map[101][101];
bool isVisited[101] = {false, };
int computerN, pairN;
int infectedN = 0;

void dfs(int node){
  isVisited[node] = true;
  for(int i=1; i<=computerN; i++){
    if(map[node][i] && !(isVisited[i])){
      infectedN++;
      dfs(i);
    }
  }
}

int main(){
  cin >> computerN >> pairN;

  for(int i=0; i<pairN; i++){
    int x, y;
    cin >> y >> x;
    map[x][y] = map[y][x] = 1;
  }

  dfs(1);

  cout << infectedN;
  return 0;
}

 

bfs

#include <iostream>
#include <queue>

using namespace std;

int map[101][101];
bool isVisited[101] = {false, };
int computerN, pairN;
int infectedN = 0;
queue<int> q;

void bfs(int node){
  q.push(node);
  isVisited[node] = true;

  while(!q.empty()){
    node = q.front();
    q.pop();

    for(int i=1; i<=computerN; i++){
      if(map[node][i]==1 && !(isVisited[i])){
        q.push(i);
        isVisited[i] = true;
        infectedN++;
      }
    }
  }
}

int main(){
  cin >> computerN >> pairN;

  for(int i=0; i<pairN; i++){
    int x, y;
    cin >> y >> x;
    map[x][y] = map[y][x] = 1;
  }

  bfs(1);

  cout << infectedN;
  return 0;
}

정리

DFS란?

DFS는 Depth First Search의 줄임말로 '깊이 우선 탐색'을 뜻한다.

트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식

재귀함수 또는 스택(stack)을 이용해 구현한다.

장점

1) 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다.

2) 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

단점

1) 해가 없는 경로에 깊이 빠질 가능성이 있다. 

2) 얻어진 해가 최단 경로가 된다는 보장이 없다. 

 

BFS란?

BFS는 Breath First Search의 줄임말로 '너비 우선 탐색'을 뜻한다.

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방식

큐(queue)를 이용해 구현한다.

장점

1) 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

단점

1) 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.

2) 해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.

3) 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

참조

https://code-kh-studio.tistory.com/30

https://tooo1.tistory.com/164

https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89?from=DFS

https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89