[백준 자바] 1260번(DFS와 BFS)

난이도 - 실버 2

문제

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

입력

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

출력

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

 

---

 

DFS (깊이 우선 탐색)

가능한 한 깊게 탐색하고 더 이상 탐색할 노드가 없으면 다시 돌아와 다른 경로를 탐색한다.

• 스택 또는 재귀 함수를 사용한다. (나는 스택을 사용했다)
• 시작 노드를 스택에 넣는다.
• 스택에서 노드 하나를 꺼낸다. (nodeIndex)
• 노드를 방문한 후(출력), 그 노드의 이웃 노드 중 방문하지 않은 노드를 역순으로 스택에 추가한다.
• 스택이 빌 때까지 반복한다.

예제 입력 1 

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

스택	1	1	4  3  2	4  3  2	4  3  4	4  3  4	4  3	4
방문		1	1	1  2	1  2	1  2  4	1  2  4  3	1  2  4  3
출력		1	1	1  2	1  2	1  2  4	1  2  4  3	1  2  4  3

 

BFS (너비 우선 탐색)

가까운 노드부터 차례대로 탐색한다.

• 큐를 사용한다.
• 시작 노드를 큐에 넣고 방문 처리한다.
• 큐에서 노드 하나를 꺼낸다. (nodeIndex, 출력)
• 그 노드의 이웃 노드들을 방문하고, 방문하지 않은 이웃 노드는 방문 처리한 후 큐에 넣는다.
• 큐가 빌 때까지 반복한다.

예제 입력 1 

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

큐	1	1	2	2  3	2  3  4	2  3  4	3  4	4
방문	1	1	1  2	1  2  3	1  2  3  4	1  2  3  4	1  2  3  4	1  2  3  4
출력		1	1	1	1	1  2	1  2  3	1  2  3  4

728x90

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

public class Main1260 {
    static class Node {
        int value;
        ArrayList<Integer> neighbors;

        Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }

        void addNeighbors(int neighbor) {
            this.neighbors.add(neighbor);
            Collections.sort(this.neighbors);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuffer sb = new StringBuffer();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        Node[] nodes = new Node[N + 1];
        for (int i = 0; i <= N; i++) {
            nodes[i] = new Node(i);
        }

        boolean[] visitedB = new boolean[N + 1];
        boolean[] visitedD = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            nodes[a].addNeighbors(b);
            nodes[b].addNeighbors(a); // 양방향 연결
        }

        for(Node i: nodes)
        System.err.println(i);

        sb.append(dfs(nodes[V], nodes, visitedD)).append('\n').append(bfs(nodes[V], nodes, visitedB));

        bw.write(sb.toString());

        bw.flush();
        br.close();
        bw.close();
    }

    private static StringBuilder bfs(Node start, Node[] nodes, boolean[] visited) {
        StringBuilder sb = new StringBuilder();

        Queue<Node> q = new LinkedList<>();

        q.offer(start);
        visited[start.value] = true;

        while (!q.isEmpty()) {
            Node nodeIndex = q.poll();
            sb.append(nodeIndex.value).append(' ');

            for (int neighbor : nodeIndex.neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.offer(nodes[neighbor]);
                }
            }
        }

        return sb;
    }

    private static StringBuilder dfs(Node start, Node[] nodes, boolean[] visited) {
        StringBuilder sb = new StringBuilder();

        Stack<Node> s = new Stack<>();

        s.push(start);

        while (!s.isEmpty()) {
            Node nodeIndex = s.pop();

            if (!visited[nodeIndex.value]) {
                visited[nodeIndex.value] = true;
                sb.append(nodeIndex.value).append(' ');

                for (int i = nodeIndex.neighbors.size() - 1; i >= 0; i--) {
                    int neighbor = nodeIndex.neighbors.get(i);
                    if (!visited[neighbor]) {
                        s.push(nodes[neighbor]);
                    }
                }
            }
        }

        return sb;
    }
}

Node 클래스

• value: 노드의 번호를 저장하는 변수
• neighbors: 노드의 이웃 노드 번호를 저장하는 리스트
• addNeighbors: 이웃 노드를 추가하고 이웃 노드 리스트를 정렬

메인 함수

• nodes 배열을 생성하여 각 노드를 초기화
• dfs함수 후에 bfs에서 초기화된 visited배열을 사용해야 하기 때문에 visited 배열을 따로 생성하였다.

 

결과)