[백준/1260] - DFS와 BFS(JAVA)

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

입력

---

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

---

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

풀이

---

public class bojtest {
    static int N, M, V;

    static ArrayList<Integer>[] arr;

    static boolean[] visited;

    static StringBuilder sb = new StringBuilder();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i=1; i<=N; i++){
           arr[i] = new ArrayList<>();
        }
        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].add(e);
            arr[e].add(s);
        }
        for (int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
        DFS(V);
        sb.append("\n");
        visited = new boolean[N+1];
        BFS(V);
        System.out.println(sb.toString());
    }
    static void DFS(int x){
        sb.append(x).append(" ");
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                DFS(i);
            }
        }
    }

    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visited[x] = true;

        while (!queue.isEmpty()){
            int i = queue.poll();
            sb.append(i).append(" ");
            for (int n : arr[i]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

해설

---

BFS와 DFS를 비교하는 문제였다.

단순히 DFS와 BFS를 돌리는 문제보다도, DFS와 BFS가 어떻게 실행되는지를 이해하고 언제 사용할 것인지를 파악하는데 도움이 되는 문제이다.

하나하나 천천히 코드를 뜯어보자.

static int N, M, V;
static ArrayList<Integer>[] arr;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();

처음 선언해줄 변수들은 DFS에서 했던 그대로 가로, 세로, 그리고 target number와

노드의 연결고리를 기록할 ArrayList 배열, 그리고 방문 배열이 필요하다.

 

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        arr = new ArrayList[N+1];
        visited = new boolean[N+1];
        for (int i=1; i<=N; i++){
           arr[i] = new ArrayList<>();
        }
        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].add(e);
            arr[e].add(s);
        }
        for (int i=1; i<=N; i++){
            Collections.sort(arr[i]);
        }
        DFS(V);
        sb.append("\n");
        visited = new boolean[N+1];
        BFS(V);
        System.out.println(sb.toString());
    }

메인 스택은 3부분으로 나눌 수 있다.

1.DFS/BFS 실행을 위해 arr과 방문 배열을 선언하고 초기화하는 것, 시작과 끝 노드를 이어주는 것

2.문제에 적힌 대로 '정점 번호가 낮은 것을 먼저 선행'하기 위해 소팅을 하는것

3.DFS를 실행하고, 방문 배열을 초기화시킨 뒤 BFS를 실행하고 출력하는 것

static void DFS(int x){
        sb.append(x).append(" ");
        visited[x] = true;
        for (int i : arr[x]){
            if (!visited[i]){
                DFS(i);
            }
        }
    }

    static void BFS(int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);
        visited[x] = true;

        while (!queue.isEmpty()){
            int i = queue.poll();
            sb.append(i).append(" ");
            for (int n : arr[i]){
                if (!visited[n]){
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

DFS와 BFS 실행이다.

DFS는 실행 번호를 적어준 뒤 방문하지 않았던 노드를 토대로 방문하는 로직이다.

BFS는 Queue를 선언하고, 큐에 노드를 넣어주는 것부터 시작된다.

다음 예를 보자.

4 5 1
1 2
1 3
1 4
2 4
3 4

<DFS 실행순서>

DFS(1)을 실행한다. arr[1]에는 2, 3이 들어있으므로 1번 방문을 체크하고 DFS(2)를 실행한다.

DFS(2)을 실행한다. arr[2]에는 4가 들어있으므로 2번 방문을 체크하고 DFS(4)를 실행한다.

DFS(4)를 실행한다. arr[4]에는 아무것도 들어있지 않으므로 4번 방문을 체크하고 스택을 종료한다.

다시 1번으로 돌아가서, 스택에 쌓여 있는 DFS(3)을 실행한다.

DFS(3)을 실행한다. arr[3]에는 4가 들어있지만 방문하였으므로 그냥 종료한다.

<BFS 실행순서>

타겟 넘버가 1일경우 1을 큐에 넣는다.

현재 큐 상태 : [1]

그리고 큐에서 다시 1을 뽑아서, 1과 연결된 노드들을 다시 큐에 넣는다. 1번 방문은 체크한다.

위의 예제에서라면 2와 3을 큐에 넣을 것이다.

큐는 FIFO 구조로 돌아가니까, 2와 3을 큐에 넣을 것이다. 2와 3번 방문은 체크한다.

현재 큐 상태 : [2 3]

빈 큐가 아니므로, poll을 하면 2번 노드가 빠진다. 2번 배열에 있는 4번 노드가 queue에 추가된다. 4번 방문은 체크한다.

현재 큐 상태 : [3 4]

빈 큐가 아니므로, poll을 하면 3번 노드가 빠진다. 3번 배열에 있는 4번 노드가 queue에 추가되어야 하나, 방문 배열에 체크되어있기 때문에 넘어간다.

현재 큐 상태 : [4]

빈 큐가 아니므로, poll을 하면 4번 노드가 빠진다. 4번 배열은 연결되어있는 노드가 없으므로 BFS를 끝낸다.

 

 

위의 예제를 기준으로, 실행순서가 DFS는 1 2 4 3이 나오고 BFS는 1 2 3 4가 나온다.

스택을 기준으로 실행하는 DFS이냐, 큐를 기준으로 실행하는 BFS이냐는 문제를 점점 풀어가며 감을 익혀가야겠지만,

한가지는 알 수 있다. BFS는 최단거리를 찾는데 유용하고, DFS는 브루트 포스같이 모든 경로를 찾는 데에 유용하다.