[TIL-25/01/20] 99클럽 코테 스터디 6일차 - 백준 1260: DFS와 BFS - JAVA

https://www.acmicpc.net/problem/1260

문제

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

 

입력

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

 

출력

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

 

접근방법

이 문제는 그래프의 기본개념과 DFS, BFS 알고리즘을 숙지하고 있는가에 대한 문제이다. 그래프의 정점, 간선이 주어지고 인접배열이나 리스트 등을 통해 그래프를 표현하고, 재귀를 이용한 DFS, 큐를 활용한 BFS 문제를 해결하면 된다.

 

코드 

package backjoon.silver.lv2;

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

public class B1260 {

    static ArrayList<Integer> graph[];
    static boolean isVisited[];

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            graph[v1].add(v2);
            graph[v2].add(v1);
        }

        // 정렬
        for (int i = 0; i < N + 1; i++) Collections.sort(graph[i]);

        isVisited = new boolean[N + 1];
        DFS(V);
        System.out.println();

        isVisited = new boolean[N + 1];
        BFS(V);
    }

    static void DFS(int v) {
        if (isVisited[v] == false) { // 방문하지 않았다면 출력하고 방문 처리
            System.out.print(v + " ");
            isVisited[v] = true;
        }
        for (int i = 0; i < graph[v].size(); i++) { // 인접 노드 탐색
            if (isVisited[graph[v].get(i)]) continue;
            DFS(graph[v].get(i));
        }
    }

    static void BFS(int root) {
        Queue<Integer> que = new LinkedList<>();

        que.add(root); // 루트 노드 Enqueue
        isVisited[root] = true;

        while (!que.isEmpty()) {
            int node = que.poll(); // Dequeue
            System.out.print(node + " ");

            for (int i = 0; i < graph[node].size(); i++) { // 인접 노드 탐색
                if (isVisited[graph[node].get(i)] == true) continue;
                que.add(graph[node].get(i)); // 인접 노드 Enqueue
                isVisited[graph[node].get(i)] = true;
            }
        }
    }

}

 

코드 분석

그래프를 인접리스트로 표현

static ArrayList<Integer> graph[];

public static void main(String[] args) throws IOException {
   ...
   
   int N = Integer.parseInt(st.nextToken());
   int M = Integer.parseInt(st.nextToken());
   
   ...
   
   graph = new ArrayList[N + 1];
   for (int i = 0; i < N + 1; i++) graph[i] = new ArrayList<>();
   
   for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        graph[v1].add(v2);
        graph[v2].add(v1);
    }
}

문제에서 `N`은 정점에 개수이다. 그러므로 리스트 배열의 크키는 정점의 개수만큼 지정해야 한다. 대신 `index`가 1부터 시작함으로 `+1`이다. 

 

그런 다음 리스트배열 내부 값에 `new ArrayList<>()`를 선언하여 각 정점 별 연결된 정점을 세팅할 수 있게된다. 세팅된 정점에 대해 간선의 개수인 `M`만큼 루프를 돌며, 값을 넣어준다. 대신 문제에서 양방향으로 설정되어 있다고 하였으니 위 코드와 같이 `v1`, `v2`를 양쪽 방향으로 삽입시켜준다.

 

DFS 구현

static boolean isVisited[];

public static void main(String[] args) throws IOException {
    ...

    isVisited = new boolean[N + 1];
    DFS(V);
}

static void DFS(int v) {
    if (isVisited[v] == false) { // 방문하지 않았다면 출력하고 방문 처리
        System.out.print(v + " ");
        isVisited[v] = true;
    }
    for (int i = 0; i < graph[v].size(); i++) { // 인접 노드 탐색
        if (isVisited[graph[v].get(i)]) continue;
        DFS(graph[v].get(i));
    }
}

재귀를 통한 DFS를 구현하였으며, 재귀가 무한정 돌지 않지 위해 방문배열 `isVisited`를 선언한다. 해당 방문 배열에 크기는 정점에 개수만큼이며 인덱스가 1부터 시작하니 `+1`로 선언한다. 

 

문제에 주어진 것처럼 `V`가 시작 정점이다. 시작 정점부터 DFS 로직을 돌게된다. 

1. 방문한 적이 없으면 방문처리를 하고 문제에 출력 조건에 따라 해당 정점을 출력한다. 
2. 해당 정점에 인접 노드를 탐색하여 방문한 적 없는 노드를 DFS 재귀로 탐색한다. 

 

BFS 구현

isVisited = new boolean[N + 1];
BFS(V);

static void BFS(int root) {
    Queue<Integer> que = new LinkedList<>();

    que.add(root); // 루트 노드 Enqueue
    isVisited[root] = true;

    while (!que.isEmpty()) {
        int node = que.poll(); // Dequeue
        System.out.print(node + " ");

        for (int i = 0; i < graph[node].size(); i++) { // 인접 노드 탐색
            if (isVisited[graph[node].get(i)] == true) continue;
            que.add(graph[node].get(i)); // 인접 노드 Enqueue
            isVisited[graph[node].get(i)] = true;
        }
    }
}

마지막으로  BFS 구현이다. BFS는 큐를 활용하며, 마찬가지로 방문배열을 이용한다. 

1. 정점을 큐에 삽입하고 해당 정점을 방문처리한다.
2. 큐가 빌때가지 루프를 돌며 큐에 들어간 노드를 `poll`한다. 이때가 실제 방문한 처리가 됨으로 출력을 같이한다. 
3. 큐에서 나온 값에 인접노드를 검색하여 방문한적 없는 노드를 큐에 담고 방문처리한다. 

 

정리

이 문제는 BFS, DFS를 한번에 정리할 수 문제이다. 코딩테스트를 준비하다보면 BFS. DFS 기본 공식 같은게 헷갈릴 때가 있는데 그때마다 찾아보면 좋은 문제인 것 같다.