[백준] 1260번 DFS와 BFS - 자바, 인접리스트 이용

전에 파이썬을 이용해 1260번을 풀어본 적이 있다.
이번에는 자바를 이용해서 1260번을 풀고, DFS와 BFS를 구현하려고 한다.
[알고리즘] 깊이우선탐색(DFS) & 너비우선탐색(BFS)

 

---

 

 

문제

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

 

입력

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

 

출력

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

 

 

---

 

 

사용한 클래스

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

public class BOJ1260 {

    static Boolean[] visited;
    // static Stack<Integer> stack = new Stack<>();
    static Queue<Integer> queue = new LinkedList<>();
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

    static StringTokenizer st;
    
    ...
}

• visited는 방문 여부를 위한 Boolean형 배열
• DFS를 위한 Stack과 BFS를 위한 Queue
• 인접 리스트로 구현하여 ArrayList의 형태를 가진 ArrayList

 

 

 

Stack을 이용한 DFS 풀이

static void DFS(int start){
    visitedFalse();
    stack.push(start);

    while(!stack.isEmpty()) {
        int idx = stack.pop();

        if(!visited[idx]){
            visited[idx] = Boolean.TRUE;
            System.out.print(idx+" ");

            for (int i : graph.get(idx)) {
                if(!visited[i])
                    stack.push(i);
            }
        }
    }
    System.out.println();
}

 

처음엔 DFS를 구현할 때 Stack을 이용해서 구현하였다.
방문한 노드를 Stack.push하고 해당 노드의 visited를 True로 변경하였다.
그리고 리스트 안의 각 리스트에 다시 접근했는데

위 방법처럼 stack을 사용하면 문제 조건인 오름차순으로 출력되지 않는다.
예제 출력인

1 2 4 3

처럼 나와야 할 내용이

1 4 3 2

로 출력되었다.
그래서 방법을 바꾸어 stack이 아닌 재귀호출을 이용했다.

 

 

재귀함수를 이용한 DFS 풀이

static void DFS(int start){
    visited[start] = Boolean.TRUE;
    System.out.print(start+" ");

    for (int idx:graph.get(start)) {
        if(!visited[idx])
            DFS(idx);
    }
}

해당 노드에 방문하지 않았으면 다시 DFS를 호출하는 간단한 방법이다.
위 방법을 사용하면 먼저 입력된 순서대로 출력이 된다.

이 먼저 입력한 순서와 오름차순을 맞추기 위해 main에서 정렬을 해주었다.

 

 

Queue를 이용한 BFS 풀이

static void BFS(int start){
    queue.add(start);

    while(!queue.isEmpty()){
        int idx = queue.poll();
        visited[idx] = Boolean.TRUE;
        System.out.print(idx+" ");

         for (int i:graph.get(idx)) {
             if(!visited[i]) {
                 queue.add(i);
                 visited[i] = Boolean.TRUE;
             }
         }
    }
}

방문하지 않은 노드는 queue에 추가하고, visited를 True로 변경한다.
queue에서 빠져나오면서 출력하면 모든 노드에 방문해 출력이 끝났을 때 queue가 비게 된다. → while(!queue.isEmpty())

 

for (int i:graph.get(idx))

위 DFS에서도 있던 이 foreach문은 콜론(:) 뒤에 있는 것을 하나씩 꺼내 앞에 넣어주게 된다.
graph는 ArrayList형태로 된 여러 ArrayList가 있다.

graph.get(idx)를 하면 해당 idx에 있는 ArrayList가 나오게 된다.
이렇게 나오게 된 ArrayList를 aList이라고 하자.

aList라는 ArrayList는 각각의 원소를 가지고 있다.
그 원소가 하나씩 i에 들어가게 된다.

 

 

메인 메서드

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

        Integer N = Integer.parseInt(st.nextToken());
        Integer M = Integer.parseInt(st.nextToken());
        Integer V = Integer.parseInt(st.nextToken());
		
//      #1.
        visited = new Boolean[N+1];
        visitedFalse();

        for (int i = 0; i < N+1; i++) {
            graph.add(new ArrayList<Integer>());
        }

//      #2.
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int edgeNode = Integer.parseInt(st.nextToken());

            graph.get(node).add(edgeNode);
            graph.get(edgeNode).add(node);
        }

//      #3.
        for (ArrayList<Integer> i:graph) {
            Collections.sort(i);
        }


        DFS(V);
        System.out.println();
        visitedFalse();
        BFS(V);

    }

    static void visitedFalse(){
        for (int i = 0; i < visited.length; i++) {
            visited[i] = Boolean.FALSE;
        }
    }

 

# 1.
이 문제는 각 인덱스 번호를 이용해 노드의 번호로 사용해 0번을 비워둔다.
그렇기 때문에 visited의 크기도 (N+1)개, graph의 크기도 (N+1)개씩 초기화 하였다.

 

# 2.
방향이 없는 무방향 그래프로 '1 2'가 입력되면
1번 노드와 2번 노드를 서로 연결되었는 것을 의미한다.

먼저 나온 node의 인덱스에 연결된 edgeNode를 추가해주고, 그 반대를 다시 진행한다.
ArrayList<ArrayList(Integer)> 형식으로 되어 있어 각 리스트의 요소가 리스트라는 것을 기억하면
어떻게 get().add()가 되는지 이해할 수 있다.

 

# 3.
위에서 말한 DFS에서 오름차순으로 출력되지 않는 문제를 해결하기 위해 정렬을 진행하였다.
문제의 '예제 입력 2'를 진행하면, 노드 연결이 오름차순 순서대로 되어 있지 않다.
이 경우 먼저 연결한 노드 순서대로 출력이 된다.

문제 조건인 '방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문'을 위해 각 노드의 리스트를 오름차순으로 정렬하면, 사용자가 어떤 순서로 노드를 연결해도 정렬을 통해 낮은 수부터 출력을 하게 된다.

 

# visitedFalse()
DFS진행 후 다시 BFS를 하기 위해 이미 사용한 visited배열을 다시 False로 초기화 시켜주었다.
좀 더 간단하게 사용하기 위해 메서드를 따로 생성하여 호출하였다.