[Algorithm] BFS, DFS

백준 2606 Java

백준 2606 바이러스를 풀던 도중 "오 문제 풀만하네!" 하고 술술 풀어서 제대로된 답이 나왔지만 틀렸다는 판정을 받았다.. 왜 틀렸는지 찾던 도중 이 문제는 BFS || DFS 를 사용해서 해결하는 문제라는것을 알게되었고 이를 공부해서 다시 풀어보겠다.

import java.io.*;
import java.util.*;

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

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

        int N  = Integer.parseInt(br.readLine());

        boolean[] arr = new boolean[N];

        arr[0] = true;

        int M = Integer.parseInt(br.readLine());

        for(int i = 0; i < M; i++ ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            int J = Integer.parseInt(st.nextToken());
            solution(arr, K, J);
        }
        int count = 0;
        for(int i = 0; i < arr.length; i++ ){
            if(arr[i]) {
                count++;
            }
        }
        if(count > 0) {
            System.out.println(count -1);
        } else {
            System.out.println(count);
        }
    }

    static void solution(boolean[] arr, int K, int J) {
        if(arr[K-1]) {
            arr[J-1] = true;
        }
    }

}

위 코드는 기존에 틀렸던 코드이다. 이런 틀린 코드가 있어야지.. 배우는게 있겠지.. 부끄러워 하지 않겠다 !!

DFS

기초 CS 를 공부하며 들어보긴 했었다 Depth First-Search (깊이 우선 탐색) 으로 알고 있다.

• 동작원리 : 스택
• 구현방법 : 재귀함수
• 시작 정점 방문 후에 다음 분기로 넘어가기 전 해당 분기를 완벽히 탐색한다.
• 노드 방문 후 자식 노드 먼저 방문한다.
• 깊게 탐색하는 방법
  - 장점 : 최선의 경우를 빠르게 찾아낸다
  • 단점 : 찾은 해가 최적의 경우가 아닐 수 있다, 최악의 경우를 찾는게 늦다.

BFS

Breath First-Search (넓이 우선 탐색) 가까운 노드부터 탐색하는 알고리즘이다.

• 동작원리 : 큐
• 구현방법 : 큐 자료 구조 사용
• 탐색 시작 노드를 큐에 쌓고 방문 처리를 한다.
• 큐에서 노드를 꺼낸 후 해당 인접 노드중에서 방문하지 않은 노드를 삽입해서 방문처리한다.

해결 코드

아래 코드를 통해 문제를 해결했다. DFS 방식을 이용해서 문제를 해결하였는데. 2차원 배열 노드를 선언해서 인접한 노드들을 탐색하는 방식? 이 조금 낯설었다 아직 제대로 코드를 짜기에는 이해는 했지만 코드응용은 어려운거같다. 조금 더 응용 문제를 풀어봐야겠다.

import java.io.*;
import java.util.*;

public class Main {
    public static int N, M;
    public static int count = 0;
    public static int[][] node;
    public static boolean[] visited;

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

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        node = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            int J = Integer.parseInt(st.nextToken());
            node[K][J] = node[J][K] = 1;
        }

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

    static void dfs(int K) {
        visited[K] = true;
        count += 1;

        for (int i = 1; i <= N; i++) {
            if (node[K][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }

}