백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘 리뷰

 

백준 2606 문제는 DFS와 BFS 중 하나를 사용해서 웜 바이러스가 걸린 컴퓨터의 댓수를 구하는 문제다. 시작점은 노드 1에서 부터 출발한다. 주어진 노드의 갯수(컴퓨터의 댓수)N과 브랜치(컴퓨터간 연결된 네트워크 갯수)M이 주어지고, 이 후 브랜치의 연결 지점을 입력받게 된다.

 

DFS는 깊이우선탐색 알고리즘으로 주어진 노드에서 가장 깊은 단말노드까지 탐색을 진행하고, 다음 노드로 이어지는 알고리즘이다. BFS는 너비우선탐색으로 동일한 깊이의 노드들을 모두 탐색하고 다음 깊이 단계로 넘어가는 알고리즘이다. 백준 2606 문제는 DFS와 BFS에 대한 개념이 있어야 한다.

 

DFS/BFS 기본 문제 리뷰

 

백준 1260 DFS와 BFS 알고리즘 자바 JAVA

 

 

백준 1260 문제는 DFS와 BFS알고리즘으로 노드 탐색 시 노드의 경로를 출력하는 문제였다. 하지만 백준 2606 문제는 연결된 지점의 노드의 갯수만 카운팅하면 되는 단순한 문제다. 

 

 

백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘

 

 

백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘

 

DFS나 BFS로 문제를 풀기 위해서는 먼저 인접행렬을 만들어줘야 한다. 좌표값에 노드가 연결되었는지를 확인하는 행렬이 생성되면 행렬값을 참조해서 재귀 함수를 사용하여 DFS를 구현하고, 큐(queue) 알고리즘을 이용한 BFS 알고리즘 접근이 가능해진다. 또한 방문한 지점을 체크하기 위해 1차 배열이 생성해줘야 한다.

 

백준 2606 필요모듈

int[][] branch	노드간 연결된 그래프를 구현하는 인접행렬
int[] visit	방문한 지점을 체크하는 1차 배열(숫자의 크기는 100)
int count	노드간 연결되어 바이러스가 감염된 컴퓨터의 댓수

 

풀이 1) DFS 모듈 사용

DFS를 사용하면 기본적으로 재귀함수를 사용하게 된다. 메소드가 호출되면 먼저 방문지점을 true로 변경하여 방문여부를 체크한다. 1부터 시작되는 순회로직에서 인접행렬의 1인지점(노드가 연결되어있다는 의미)와 방문하지 않은 지점(visit[x]=false) 에서 컴퓨터가 바이러스에 걸렸다는 의미로 counitng을 해주고 다시 재귀함수가 호출되면서 노드의 깊이가 깊어진다.

 

풀이 2) BFS 모듈 사용

큐(Queue)를 생성해주고, 최초 방문 지점을 체크한다. 최초 시작노드를 큐에 add() 해주고 큐가 모두 빌 때 까지 순회과정이 진행된다. 큐에서 한개의 노드를 출력하고 인접행렬에서 1인지점과 방문하지 않은 지점을 찾는다. 해당 지점에서 바이러스에 걸린 컴퓨터를 카운팅하고 해당 노드를 큐에 입력한 후 방문 여부를 체크해준다.

 

 

JAVA CODE

/*
    Owner : Developer Blog
    Title : 백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘
    Algorithm : DFS/BFS 알고리즘
    Date : 2022-03-03
*/

import java.util.*;

public class A_2606 {
    public static int N;
    public static int M;
    public static int[][] branch;
    public static boolean[] visit;
    public static int count;
    public static Queue<Integer> queue;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        N = in.nextInt();
        M = in.nextInt();
        branch = new int[101][101];
        visit = new boolean[101];

        // 인접행렬 생성 
        for(int i=1; i<M+1; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            branch[a][b] = branch[b][a] = 1;
        }

        // dfs(1);
        bfs(1);
        System.out.println(count);
    }
    public static void dfs(int start){
        visit[start]=true;
        
        
        for(int j=1; j<N+1; j++){
            if(branch[start][j]==1 && visit[j]==false){
                count++;
                dfs(j);
            }
        }       
    }

    public static void bfs(int start){
        queue = new LinkedList<Integer>();

        visit[start] = true;
        queue.add(start);

        while(!queue.isEmpty()){
            int temp = queue.poll();
            for(int j=1; j<N+1; j++){
                if(branch[temp][j]==1 && visit[j]==false){
                    count++;
                    queue.add(j);
                    visit[j] = true;
                }
            }       

        }
    }
}

 

 

백준 2606 결과

DFS와 BFS로 풀어본 결과 확실히 메모리는 DFS가 더 많이 사용하지만 시간은 더 빨랐다. BFS는 동일 깊이의 노드들을 순회하면서 탐색이 진행되기 때문에 DFS보다는 속도면에서 느릴 수 있다. 하지만 노드의 갯수가 폭발적으로 증가하게 되면 필요없는 노드의 깊이 까지 들어가기 때문에 안정성 면에서 BFS 알고리즘을 권장한다.

백준 2606 바이러스 자바 JAVA DFS BFS 알고리즘

 

 

 

 

더 읽을거리

 

백준 1780 종이의 개수 알고리즘 자바 JAVA

 

백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바

 

백준 알고리즘 2630번 분할정복 색종이 만들기 자바 JAVA