Java 백준 문제풀이 (32) 1260: DFS와 BFS

 

오늘도 날로 먹는 문제로 찾아왔다.

코드스테이츠에서 알고리즘을 과정을 진행하고 있어서 진 빠진다.

 

DFS와 BFS의 기본 코드 작성법을 익히고 차이점을 눈으로 직접 확인하기 좋은 문제이다.

이 문제를 풀려고 시도하는 사람이 DFS와 BFS에 대해 전혀 모를리는 없으므로 기억이 흐릿할 때 보기 좋은 이미지를 첨부하는 것으로 이해를 돕도록 하겠다.

 

 

 

 

 

 

 

1. dfs

public static void dfs(int v) {
    visited[v] = true;
    sb.append(String.valueOf(v)).append(" ");

    // 현재 정점과 연결된 정점 탐색 -> 해당 정점과 연결된 -> 연결된 -> ...
    for (int n : edges.get(v)) {
        if ( !visited[n] ) {
            dfs(n);
        }
    }
}

 

dfs는 연결된 정점을 모조리 탐색한다.

 

 

 

 

 

 

2. dfs

 

public static void bfs(int v) {
    queue.add(v);
    checked[v] = true;
    while ( !queue.isEmpty() ) {
        // 현재 노드 - 큐의 가장 앞에 있는 노드
        int current = queue.poll();
        sb.append(current).append(" ");
        // 1레벨과 연결된 2레벨 탐색, 2레벨과 연결된 3레벨 탐색, .. 반복
        for (int n : edges.get(current)) {
            if (!checked[n]) {
                queue.add(n);
                checked[n]=true;
            }
        }
    }
}

 

bfs는 레벨별 (연결되어 있는 순서)로 탐색한다.

bfs는 헷갈리면 그래프부터 보기보다는 트리를 생각하는 게 쉽다.

1층부터 내려가면서 한 층씩 탐색한다고 생각하면 된다.

 

 

 

 

 

 

 

3. 정답

 

 

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

public class Main {
    static ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
    static LinkedList<Integer> queue = new LinkedList<>();
    static StringBuilder sb = new StringBuilder();
    public static boolean[] visited;
    static boolean[] checked;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // 정점 수, 간선 수, 시작점
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());

        // 시작점이 1이므로 <=으로 반복문을 돌린다.
        for (int i=0; i<=V; i++) {
            edges.add(new ArrayList<>());
        }

        // 무방향(양방향) 그래프이다.
        for (int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int edge1 = Integer.parseInt(st.nextToken());
            int edge2 = Integer.parseInt(st.nextToken());

            edges.get(edge1).add(edge2);
            edges.get(edge2).add(edge1);

        }

        // 오름차순으로 방문한다
        for (int i=0; i<=V; i++) {
            Collections.sort(edges.get(i));
        }

        // 시작 정점이 1이므로 +1
        visited = new boolean[V+1];
        checked = new boolean[V+1];

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

        System.out.println(sb.toString());
    }

    public static void dfs(int v) {
        visited[v] = true;
        sb.append(String.valueOf(v)).append(" ");

        for (int n : edges.get(v)) {
            if ( !visited[n] ) {
                dfs(n);
            }
        }
    }

    public static void bfs(int v) {
        queue.add(v);
        checked[v] = true;
        while ( !queue.isEmpty() ) {
            // 현재 노드 - 큐의 가장 앞에 있는 노드
            int current = queue.poll();
            sb.append(current).append(" ");
            for (int n : edges.get(current)) {
                if (!checked[n]) {
                    queue.add(n);
                    checked[n]=true;
                }
            }
        }
    }
}