6-1: 깊이우선탐색, 너비우선탐색

깊이우선탐색과 너비우선탐색

 

문제

---

그래프가 주어질 때, 0번 정점을 시작으로 하여 깊이우선탐색과 너비우선탐색의 결과를 출력하는 프로그램을 작성하시오. 단, 노드를 방문할 때는 노드 번호가 작은 순서대로 방문한다고 하자.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다.

 

출력

---

첫 번째 줄에 깊이우선탐색 결과, 두 번째 줄에 너비우선탐색 결과를 출력한다.

 

예제 입력

9 12
0 1
0 2
0 3
1 5
2 5
3 4
4 5
5 6
5 7
5 8
6 7
7 8

예제 출력

0 1 5 2 4 3 6 7 8
0 1 2 3 5 4 6 7 8

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class bfsdfs {
    /**
     *
     *
     *
     *
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numNodes = sc.nextInt();
        int numEdges = sc.nextInt();

        Graph graph = new Graph(numNodes);

        //add nodes
        for (int i=0; i<numNodes; i++){
            Node node = new Node(i);
            graph.nodeArr[i] = node;
        }

        //add edges
        for (int i=0; i<numEdges;i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            graph.adjacencyMatrix[start][end] = true;
            graph.adjacencyMatrix[end][start] = true;
        }

        dfs(graph, graph.nodeArr[0]);
        System.out.println();
        //clear visited
        for (int i=0; i<numNodes; i++){
            graph.nodeArr[i].visited = false;
        }
        bfs(graph, graph.nodeArr[0]);
    }

    private static void dfs(Graph graph, Node start) {
        if (start == null){
            return;
        }

        ArrayDeque<Node> stack = new ArrayDeque<>();
        stack.push(start);

        while(!stack.isEmpty()){
            Node temp = stack.pop();
            if (!temp.visited){
                System.out.print(temp.data + " ");

                temp.visited = true;
//                System.out.print(temp.data + " ");
                //look at its edges, and push onto stack.
                for (int i=0; i<graph.adjacencyMatrix[temp.data].length; i++){
                    if (graph.adjacencyMatrix[temp.data][graph.adjacencyMatrix[temp.data].length-i-1]){
                        //is edge.
                        stack.push(graph.nodeArr[graph.adjacencyMatrix[temp.data].length-i-1]);
                    }
                }
            }
        }
    }

    private static void bfs(Graph graph, Node start) {
        if (start == null){
            return;
        }

        LinkedList<Node> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()){
            Node temp = queue.remove();
            if (!temp.visited){
                System.out.print(temp.data + " ");

                temp.visited = true;
//                System.out.print(temp.data + " ");
                //look at its edges, and push onto stack.
                for (int i=0; i<graph.adjacencyMatrix[temp.data].length; i++){
                    if (graph.adjacencyMatrix[temp.data][i]){
                        //is edge.
                        //enqueue in order
                        queue.add(graph.nodeArr[i]);
                    }
                }
            }
        }
    }

    public static class Graph{

        Node[] nodeArr;
        boolean[][] adjacencyMatrix;

        public Graph(int N){
            nodeArr = new Node[N];
            adjacencyMatrix = new boolean[N][N];
        }
    }

    public static class Node{
        int data;
        boolean visited;

        public Node(int data){
            this.data = data;
        }
    }
}