[Algorithm study] 백준 1260

문제 출처 : https://www.acmicpc.net/problem/1260

DFS(Depth-First Search)

DFS는 깊이 우선 탐색이며 그래프나 트리를 탐색할 때 탐색 우선 순위를 다음 level 즉, 자신의 자식노드를 우선 순위로 방문하는 탐색방법입니다.

DFS의 동작 과정은 다음과 같습니다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스텍이 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

이를 간단하게 예시를 들어 설명하면 다음과 같습니다. (방문 기준: 정점번호가 작은 수 우선)

위의 그림과 같이 정점 1에서 탐색을 시작한다고 하면 가장먼저 1을 방문처리 후 스택에 넣습니다.
정점 1의 다음 level(자식 노드)에는 2와 3이 있는데 정점번호가 작은 수 우선 방문이므로 2를 방문처리 후 스택에 넣습니다.
정점 2의 다음 level(자식 노드)에는 4와 5가 있는데 위와 같은 이유로 4를 방문처리 후 스택에 넣습니다.
정점 4에서 방문할 수 있는 노드가 없으므로 스택에서 4을 빼냅니다.
다시 정점 2에서 방문할 수 있는 노드는 4와 5가 있는데 4는 방문처리 되었으므로 5를 방문처리하고 스택에 5를 넣습니다.
정점 5에서 방문 가능한 노드는 2와 3이 있는데 2는 방문처리 된 노드이므로 3을 방문처리하고 3을 스택에 넣습니다.
정점 3에서 방문 가능한 노드는 1,5,6이 있는데 1,5는 방문 처리 되었으므로 6을 방문처리하고 6을 스택에 넣습니다.

모든 노드가 방문되었고 깊이 우선 탐색(DFS)로 방문된 노드 순서는
1 -> 2 -> 4 -> 5-> 3-> 6 입니다.

BFS(Breath-First-Search)

BFS는 너비 우선 탐색이며 그래프나 트리를 탐색할 때 탐색 우선 순위를 같은 level의 노드를 우선 순위로 방문하는 탐색방법입니다.

BFS의 동작 과정은 다음과 같습니다.
1. 탐색 시작 노드를 큐에 삽입하고 방문처리 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

이를 간단하게 예시를 들어 설명하면 다음과 같습니다.(방문기준: 정점번호가 작은 수)

위의 그림과 같이 정점 1에서 탐색을 시작한다고 하면 가장먼저 1을 방문처리 후 큐에 1을 넣습니다.
1을 큐에서 꺼낸 후 1과 인접한 정점 2와 3을 방문처리 한 후 큐에 삽입합니다.(방문기준에 따라 2를 먼저 큐에 삽입합니다.)
2를 큐에서 꺼낸 후 2와 인접한 정점 4와 5를 방문처리 한 후 큐에 삽입합니다.(방문기준에 따라 4를 먼저 큐에 삽입합니다.)
3을 큐에서 꺼낸 후 3과 인전한 정점 1,5,6에서 1과 5는 방문처리 된 정점이므로 6을 방문처리한 후 큐에 삽입합니다.

모든 노드가 방문되었고 너비 우선 탐색(BFS)로 방문된 노드 순서는
1 -> 2 -> 3 -> 4-> 5-> 6 입니다.

문제 접근

dfs와 bfs의 알고리즘을 각각의 함수로 정의하여 위의 문제를 해결했다.
단, 문제에서 정점 번호가 작은 수부터 방문하라는 조건이 있어 이점을 유의하며 함수를 선언했다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_1260 {
    static ArrayList<ArrayList<Integer>> map;
    static boolean[] visited_dfs;
    static boolean[] visited_bfs;
    static int cnt;
    static int N;
    static int M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        map = new ArrayList<ArrayList<Integer>>();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        visited_dfs = new boolean[N+1];
        visited_bfs = new boolean[N+1];
        cnt = 0;
        for(int i = 0; i <= N; i++){
            map.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            map.get(p).add(q);
            map.get(q).add(p);
        }
        dfs(start);
        System.out.println();
        bfs(start);
    }
    public static void dfs(int x){
        visited_dfs[x] = true;
        System.out.print(x+" ");
        map.get(x).sort(Comparator.naturalOrder());
        for(int i : map.get(x)){
            if(!visited_dfs[i])
                dfs(i);
        }
    }

    public static void bfs(int x){
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(x);
        visited_bfs[x] = true;
        while(!q.isEmpty()){
            int y = q.poll();
            System.out.print(y+" ");
            map.get(y).sort(Comparator.naturalOrder());
            for(int i : map.get(y)){
                if(!visited_bfs[i]){
                    q.offer(i);
                    visited_bfs[i] = true;
                }
            }
        }
    }
}