DFS, BFS 구현방법 ( + [백준] 2606 바이러스 문제풀이)

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

2606번: 바이러스

 

 

 

DFS (Depth-First Search)

DFS는 깊이 우선 탐색이다. 

아래 그림처럼 한 곳만 깊게~ 계속 파다가 끝이 나오면, 다른 곳으로 가서 다시 깊게~ 계속 파는 것이다.

https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

 - 단순 검색은 BFS보다 느리다

 - 모든 곳을 방문할 때 자주 사용된다.

 - 재귀함수를 사용하여 다음 탐색 노드(현재 노드와 인접하고, 방문한 적이 없는 노드)로 이동한다.

 

BFS (Breadth-First Search)

BFS는 너비 우선 탐색이다.

아래 그림처럼 옆으로 넓게~ 하나씩 살펴보고 찾는 값이 없으면, 한 단계 깊게 들어가서 다시 넓게~ 살펴보는 것이다.

https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

 - 단순 검색은 DFS보다 빠르다.

 - 최단경로를 찾을 때 자주 사용된다

 - Queue를 사용하여 다음 탐색 노드(현재 노드와 인접하고, 방문한 적이 없는 노드)를 저장한다. 

 

 

DFS 문제풀이

node[a][b] = node[b][a] = 1 

 : 각 노드들은 방향성이 없다. 방향성이 없으니 2번에서 5번으로 갈수도, 5번에서 2번으로 갈수도 있다.

 : 대칭좌표를 입력해주면 좀 더 쉽게 탐색이 끝날 수 있다.

 

dfs 부분은 주황색부분에 자세하게 적어놨으니 코드를 따라 읽어보면 자연스럽게 이해될것이다!

dfs 함수를 재귀적으로 호출하면서 더 깊게 탐색한다

 

DFS 제출코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main2606_dfs {
    /*
    7       //컴퓨터의 수
    6       //네트워크에 연결되어있는 컴퓨터 쌍의 수
    1 2     // 1-2 연결됨
    2 3     // 2-3 연결됨
    1 5     // 1-5 연결됨
    5 2     // 5-2 연결됨
    5 6     // 5-6 연결됨
    4 7     // 4-7 연결됨
    * */
    static int[][] node;
    static boolean[] check; //바이러스에 감염되었는지
    static int count = 0;   //감염 컴퓨터 수
    static int computers;
    static int pairs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        computers = Integer.parseInt(br.readLine());
        pairs = Integer.parseInt(br.readLine());

        node = new int[computers+1][computers+1];
        check = new boolean[computers+1];
        for (int i = 0; i < pairs; i++) {
             StringTokenizer st = new StringTokenizer(br.readLine(), " ");
             int a = Integer.parseInt(st.nextToken());
             int b = Integer.parseInt(st.nextToken());
             node[a][b] = 1;
             node[b][a] = 1;
             //방향성이 없기때문에
        }

        dfs(1);
        System.out.println(count-1);

    }


    public static void dfs(int start) {
        check[start] = true;    // 1번 (start) 감염
        count++;    //감염된 컴퓨터 수 증가

        for (int i = 0; i <= computers; i++) {  //컴퓨터 개수만큼 반복
            if (node[start][i] == 1 && !check[i]) {    //node[start][i] == 1 : 1번(start)과 연결된 노드라면     //!check[i] : i번 컴퓨터가 감염되지 않았다면
                dfs(i); // i번 컴퓨터 감염처리리            
            }
        }
    }

}

 

 

 

BFS 문제풀이

node[a][b] = node[b][a] = 1

 : 각 노드들은 방향성이 없다. 방향성이 없으니 2번에서 5번으로 갈수도, 5번에서 2번으로 갈수도 있다.

 : 대칭좌표를 입력해주면 좀 더 쉽게 탐색이 끝날 수 있다.

 

bfs 부분은 주황색부분의 흐름을 따라가보자!

bfs 함수는 1번만 호출되고, 노드를 탐색하면서 다음에 어떤 노드를 탐색할 것인지를 queue에 저장한다.

현재 노드 탐색이 끝나면, queue에 저장해둔 노드를 꺼내어 탐색한다.

 

 

BFS 제출코드

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main2606_bfs {
    /*
    7       //컴퓨터의 수
    6       //네트워크에 연결되어있는 컴퓨터 쌍의 수
    1 2     // 1-2 연결됨
    2 3     // 2-3 연결됨
    1 5     // 1-5 연결됨
    5 2     // 5-2 연결됨
    5 6     // 5-6 연결됨
    4 7     // 4-7 연결됨
    * */
    static int[][] node;
    static boolean[] check; //바이러스에 감염되었는지
    static int count = 0;   //감염 컴퓨터 수
    static Queue<Integer> queue = new LinkedList<>();
    static int computers;
    static int pairs;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        computers = Integer.parseInt(br.readLine());
        pairs = Integer.parseInt(br.readLine());

        node = new int[computers+1][computers+1];
        check = new boolean[computers+1];
        for (int i = 0; i < pairs; i++) {
             StringTokenizer st = new StringTokenizer(br.readLine(), " ");
             int a = Integer.parseInt(st.nextToken());
             int b = Integer.parseInt(st.nextToken());
             node[a][b] = 1;
             node[b][a] = 1;
             //방향성이 없기때문에
        }

        bfs(1);
        System.out.println(count);

    }

    public static void bfs(int start) {
        queue.offer(start);
        check[start] = true;    // 1번 (start) 감염

        while(!queue.isEmpty()){
            int temp = queue.poll();
            for (int i = 0; i <= computers; i++) {
                 if(node[temp][i] == 1 && !check[i]) {
                     queue.offer(i);
                     check[i] = true;
                     count++;
                 }
            }
        }
    }

}