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

 

 

 

백준 1260번 문제는 DFS(깊이우선탐색)과 BFS(넓이우선탐색) 알고리즘을 이해하는 문제다. 비선형 자료구조인 트리구조에서 탐색을 하기 위해서는 노드(node)와 브랜치(branch)를 이동하면서 각각의 노드값을 기록해야 한다.

 

DFS(Depth First Search, 깊이우선탐색)

깊이우선 탐색은 노드의 깊이가 깊은 순서를 먼저 탐색하는 알고리즘이다. 노드의 시작은 1부터 시작하고, 가장 깊은 곳의 노드까지 방문을 마치면 다음 자식노드로 이동해서 노드의 끝가지 이동하게 된다. DFS 알고리즘은 인접행렬 자료구조와 재귀 알고리즘을 사용해서 구현 가능하다.

출처 : 위키백과

 

DFS를 구현하기 위해 사용되는 인접행렬은 대칭행렬의 모습을 가지고 있다. 백준 1260번에서 처음 입력값을 유한 그래프로 표시하면 아래와 같다. 노드 1은 2,3,4와 브랜치를 가진다. 노드 2는 1,4를, 노드3은 1과 4에 연결된다. 노드 4는 2와3과 연결되어 있다. 

 

노드1부터 노드4까지 연결된 브랜치가 존재하면 1, 존재하지 않으면 0으로 표시한 행렬값은 아래와 같다. 정점에서 숫자가 작은 노드 부터 방문한다는 규칙이 있기 때문에, DFS 알고리즘으로 검색하면 1,2,4,3의 결과값이 나오게 되는 것이다. 

 

노드 방문 순서

첫번째 : 노드 1에서 노드 2로 이동(노드값이 가장 작은 곳이 2임)  >>> 결과값 1,2

두번째 : 노드 2에서 노드 4로 이동(노드 1은 이미 방문했고, 노드 4밖에 없음) >>> 결과값 1,2,4

세번째 : 노드 4에서 노드 3로 이동(노드 1,2는 이미 방문했고, 노드 4밖에 없음) >>> 결과값 1,2,4,3

 

 

BFS(Breadth First Search, 너비우선탐색)

너비 우선탐색은 같은 깊이의 노드를 먼저 탐색하는 알고리즘이다. 시작정점에서 출발하여 같은 깊이 노드들을 우선적으로 탐색하고 한개의 깊이가 완료되면 다음 깊이로 이동해서 검색하게 된다. 너비 우선탐색 알고리즘은 Queue 자료구조를 사용해서 구현 가능하다.

인접행렬에서 노드 1에서 담을 수 있는 노드2, 노드3, 노드4의 값들을 큐 자료구조에 넣으면서 방문 기록을 남김과 동시에 방문한 노드값을 출력한다. 큐에 담긴 노드값들을 순차적으로 poll() 하면서 큐 자료를 삭제하면서 다음 노드값으로 이동한다. 동일 깊이의 노드값들을 순회하면서 마지막 노드에 다다르게 된다. 

 

 

 

 

JAVA CODE

/*
    Owner : Developer Blog
    Title : DFS와 BFS
    Algorithm : DFS, BFS 탐색 알고리즘
    Date : 2022-03-02
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

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

    public static void dfs(int start){
        visit[start] = true;
        System.out.print(start + " ");
        for(int i=1; i<=N; i++){
            if(branch[start][i]==1 && visit[i]==false){
                    dfs(i); 
            }
        }
    }
    public static void bfs(int start){
        queue = new LinkedList<Integer>();
        queue.add(start);
        visit[start] = true;
        System.out.print(start + " ");

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

            for(int i=1; i<branch.length; i++){
                if(branch[temp][i]==1 && visit[i]==false){
                    queue.add(i);
                    visit[i]=true;
                    System.out.print(i+" ");
                }
            }
        }
    }

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

        branch = new int[1001][1001];
        visit = new boolean[1001];

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

		// 정점은 1로 부터 DFS 시작
        dfs(V);
        System.out.println();
        
        // DFS가 완료되면 visit list 초기화 해줘야됨
        Arrays.fill(visit, false);
        // 정점은 1로 부터 DFS 시작
        bfs(V);


    }
    
}

 

결과

메모리 42MB, 0.612초가 소요되었고 맞았습니다.