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

깊이우선탐색과 너비우선탐색 (bfsdfs.cpp)

 

문제

---

그래프와 그래프를 이루고 있는 한 정점이 주어질 때, 그 정점으로부터 깊이 우선 탐색과 너비 우선 탐색을 하고 탐색한 순서대로 정점들을 출력하는 프로그램을 작성하시오. 만약 한 정점에서 갈 수 있는 정점이 여러 개일 경우 알파벳 순으로 빠른 정점을 우선한다.

 

입력

---

입력 파일의 첫 번째 줄에는 정의 개수 N과 간선의 개수 E가 주어진다. 정점은 A부터 차례대로 알파벳 대문자로 표현된다. 이어 E줄에 걸쳐 간선들의 정보가 주어지는데 간선의 정보는 간선의 두 양끝 정점으로 표현된다. 마지막 줄에는 탐색을 시작할 정점이 주어진다. N은 26 이하의 자연수, E는 100 이하의 자연수이며 그래프는 하나로 연결되어 있다.

 

출력

---

출력 파일의 첫째 줄에는 깊이 우선 탐색을 한 결과를, 둘째 줄에는 너비 우선 탐색을 한 결과를 출력한다.

 

예제 입력

7 9
A B
B E
A E
B C
E F
C F
C D
D G
G F
A

예제 출력

ABCDGFE
ABECFDG

코드

//트리순회

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static ArrayList<Node> box = new ArrayList<>();
    public static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        char c;
        char d ;
        char start;

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

        Node node;

        a = sc.nextInt();
        b = sc.nextInt();

        for(int i = 0; i<a ;i++) {
            box.add(new Node((char)(65+i)));
        }

        for(int i = 0 ; i < b ; i++) {
            c = sc.next().charAt(0);
            d = sc.next().charAt(0);
            node = findeNode(c);
            node.getNodes().add(findeNode(d));
        }

        start = sc.next().charAt(0);
        node = findeNode(start);

        dfs(node);
        System.out.println("");

        for(int i = 0 ; i < box.size() ; i++) {
            box.get(i).setChecked(false);
        }

        node = findeNode(start);

        q.offer(node);
        bfs(q);
        System.out.println("");


    }

    public static void dfs(Node node) {


        if(!node.isChecked()) {
            System.out.print(node.getData());

            node.setChecked(true);

//            node.getNodes().sort(new NewComp());

            for(int i = 0 ; i < node.getNodes().size() ; i ++) {
                dfs(node.getNodes().get(i));
            }
        }


    }



    public static void bfs(Queue<Node> q) {
        Node node;
        ArrayList<Node> datas;

        while (!q.isEmpty()) {
            node = q.poll();
            System.out.print(node.getData());
            datas = node.getNodes();

//            datas.sort(new NewComp());

            for (Node data:
                 datas) {
                if(!data.isChecked()) {
                    q.offer(data);
                    data.setChecked(true);
                }

            }
        }

    }


    public static Node findeNode(char key) {

        for(int i = 0 ; i < box.size() ; i++) {
            if(box.get(i).getData() == key) {
                return box.get(i);
            }
        }
        return new Node(key);
    }


}

class NewComp implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        Node a  = (Node) o1;
        Node b  = (Node) o2;
        return (int)a.getData() - (int)b.getData();
    }
}

class Node {
    private char data;
    private ArrayList<Node> nodes;
    private boolean isChecked;

    public boolean isChecked() {
        return isChecked;
    }

    public void setChecked(boolean checked) {
        this.isChecked = checked;
    }

    public Node(char data) {
        this.data = data;
        this.nodes = new ArrayList<>();
        this.isChecked = false;
    }

    public char getData() {
        return data;
    }

    public ArrayList<Node> getNodes() {
        return nodes;
    }

}