[백준 1260 : JAVA] DFS와 BFS / DFS, BFS

개요

 

dfs와 bfs는 둘타 탐색을 하는데 사용된다.

dfs는 깊이 우선 탐색으로 스택 또는 재귀함수를 구현한다.

bfs는 너비 우선 탐색으로 큐로 구현한다. 

(예전에 bfs를 처음 배울 때 물에 돌을 떨어 뜨렸을 때 파장과 같이 점차적으로 모든 방향을 동시에 탐색하고 나간다고 배웠는데 아직도 기억에 남는다...)

 

뭐 삼성 코테에서 주를 이루고 있는 문제라고 할 수 있다.

물론 난이도는 이문제보다는 높은 문제들이 많다..

 

이 문제는 dfs, bfs 두 가지 방식으로 풀 수 있다는 것을 보여주고 있다.

 

문제

 

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

 

풀이

 

DFS - 스택이나 재귀함수로 풀 수 있다.

 

• 한 노드에서 갈 수 있는 노드 중 하나를 선택한다
• 선택한 노드에서 갈 수 있는 노드 중 하나를 선택한다. 이 때 이미 방문한 노드는 제외하고 선택한다.
• 갈 수 있는 노드가 존재하지 않으면 이전 노드로 돌아와서 갈 수 있는 노드 중 하나를 선택한다.

     위의 시퀀스가 반복되며 경로를 탐색한다.

 

BFS - 큐로 풀 수 있다.

 

• 한 노드에서 갈 수 있는 노드를 큐에 추가한다.
• 큐에서 노드를 하나 꺼내어 꺼낸 노드에서 갈 수 있는 노드를 큐에 추가한다.
• 큐에 노드가 존재하지 않으면 break한다.

     위의 시퀀스가 반복되며 경로를 탐색한다.

 

     DFS는 한노드에서 끝까지 꼬리를 물고 탐색하지만 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 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] arr;
    static boolean[] check;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        arr = new int[n + 1][n + 1];
        check = new boolean[n + 1];
        
        // 노드와 간선에 대한 값을 초기화
        for(int i = 0 ; i < m; i++){
            st= new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            arr[s][e] = 1;
            arr[e][s] = 1;
        }

        dfs(v);
        sb.append("\n");
        bfs(v);

        System.out.println(sb);
    }
    
    // check배열 false로 초기화
    public static void initCheck(){
        for(int i = 0 ; i < check.length; i++) check[i] = false;
    }

    //dfs 메소드
    public static void dfs(int start){
        // 경로 출력
        sb.append(start + " ");
        // 현재 노드 방문 처리
        check[start] = true;

        for(int i = 1; i < check.length; i++)
            // 현재 노드와 다른 노드 중 && 미방문 && 간선이 존재
            if(i != start && check[i] == false && arr[start][i] == 1)
                dfs(i);

    }
    public static void bfs(int start){
        // check배열 초기화
        initCheck();
        Queue<Integer> queue = new LinkedList<>();

        // 처음 시작노드 추가
        queue.add(start);
        // 처음 시작노드 방문처리
        check[start] = true;

        while(!queue.isEmpty()){
            int num = queue.poll();
            sb.append(num + " ");

            for(int i = 1; i < check.length; i++){
                // 현재 노드와 다른 노드 중 && 미방문 && 간선이 존재
                if(i != num && check[i] == false && arr[num][i] == 1) {
                    // 노드 추가
                    queue.add(i);
                    check[i] = true;
                }
            }
        }
        sb.append("\n");
    }
}