[백준]2606 바이러스

야심차게 코테 공부 시작 !!!

이 문제는 DFS, BFS 두 가지 방식으로 풀 수 있는 문제이다.
잘 몰라서 풀이봤다 ^^; ..

• 그래프 탐색 알고리즘(DFS/BFS)
  여러 개체들이 연결되어 있는 자료구조에서 특정 개체를 찾기 위한 알고리즘을 말한다.

1. 경로탐색 유형(최단거리, 시간)
2. 네트워크 유형(연결)
3. 조합 유형(모든 조합 만들기)

• DFS

package baekjoon;

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

public class baekjoon2606 {
    static boolean [][] dfs;
    static boolean [] check;
    static int count=0;
    static int N;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());        // 컴퓨터 대
        int M = Integer.parseInt(br.readLine());        // 연결 쌍

        dfs = new boolean[N+1][N+1];
        check = new boolean[N + 1];

        int cnt = 0;
        while(cnt < M) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            dfs[n][m] = true;
            dfs[m][n] = true;
            cnt ++;
        }

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

    static void dfs(int i) {
        check[i] = true;
        count++;

        for (int j = 0; j <= N; j++) {
            if(dfs[i][j] && !check[j]) {
                dfs(j);
            }
        }
    }
}

💡 DFS는 깊이 우선 탐색 방식으로 루트 노드에서 시작해 다음 분기로 넘어가기 전까지 해당 분기를 완벽하게 탐색하는 방법이다.
재귀함수를 사용하여 구현한다.
수행관점에선 복불복이기 때문에 시간초과의 이슈가 있다.

연결된 네트워크 상의 컴퓨터 번호를 dfs 배열에 모두 담아준다. 1번 컴퓨터로부터 감염된 컴퓨터를 찾아야하므로 dfs(1)을 호출하여 시작한다.

1번 컴퓨터로부터 연결된 컴퓨터들의 check 값이 true로 켜지게 되고, 연결된 컴퓨터의 dfs가 호출되어 감염 카운트가 올라간다.

1번 컴퓨터 호출 -> 카운트 +1 -> 연결된 컴퓨터 호출 -> 카운트 +1 -> ...

dfs 재귀함수가 호출되는 i,j 값은 이렇다.
1 2
2 3 -> 3번은 check 값은 켜지지만 dfs 배열에 없으므로 카운트 안됨
2 5
5 6

• BFS

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 Main {
    static boolean [][] bfs;
    static boolean [] check;
    static int count=0;
    static int N;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());        // 컴퓨터 대
        int M = Integer.parseInt(br.readLine());    // 연결 쌍

        bfs = new boolean[N+1][N+1];                // bfs로 풀기

        check = new boolean[N + 1];

        int cnt = 0;
        while(cnt < M) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            bfs[n][m] = true;
            bfs[m][n] = true;
            cnt ++;
        }

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

    static int bfs(int i) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(i);
        check[i] = true;

        while(!q.isEmpty()) {
            int temp = q.poll();

            for(int k = 1; k<=N; k++) {
                if (bfs[temp][k] && !check[k]) {
                    q.offer(k);
                    check[k] = true;
                    count++;
                }
            }
        }

        return count;
    }

}

💡 BFS는 너비 우선 탐색 방식으로 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법이다.
큐나 링크드 리스트를 사용하여 구현한다.
시간복잡도가 낮아 규모가 큰 경우에 주로 사용한다.

비슷한 방법이다. bfs 배열안에 연결된 컴퓨터 번호 모두 담아주고, 1번 컴퓨터부터 호출 시작한다.

q안에 1번이 담기고 연결된 컴퓨터와 호출된 이력을 체크하여 q에 계속 담아준다. q가 비워질 때까지 반복되므로 dfs 와 같은 방식으로 체크하여 값을 도출해낸다.

😵‍💫 그래프 탐색 알고리즘은 익숙해질 때까지 많이 풀어봐야 할 것 같다 ,, ㅠ 그날이 올때까지 열 코딩