백준 1260번

문제 이름 및 분류

---

이름: DFS와 BFS
알고리즘 분류: DFS, BFS

문제

---

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

입력

---

첫째 줄- 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V

다음 M개의 줄- 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

---

첫째 줄- DFS를 수행한 결과

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

풀이

---

먼저, 입력값으로 그래프를 만든다. 인접 리스트로 구현한다.
그 다음, DFS 수행결과를 작성하는데 자료구조는 스택을 사용하여 반복문으로 구현한다.
그 다음, BFS 수행결과를 작성하는데 자료구조는 큐를 사용하여 반복문으로 구현한다.

코드

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException{
        Scanner scan= new Scanner(System.in);
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringBuilder result= new StringBuilder();
        List<List<Integer>> graph= new ArrayList<>();
        int vertexCount, lineCount, startVertexNum, fromVertex, toVertex, currentVertex;
        Stack<Integer> dfsRoute= new Stack<>();
        Queue<Integer> bfsRoute= new LinkedList<>();
        boolean[] isVisitedDfs, isVisitedBfs;

        vertexCount= scan.nextInt();
        lineCount= scan.nextInt();
        startVertexNum= scan.nextInt();
        isVisitedDfs= new boolean[vertexCount+1];
        isVisitedBfs= new boolean[vertexCount+1];
        for(int i=0; i<=vertexCount; i++){
            graph.add(new ArrayList<>());
        }

        for(int i=1; i<=lineCount; i++){
            fromVertex= scan.nextInt();
            toVertex= scan.nextInt();
            graph.get(fromVertex).add(toVertex);
            graph.get(toVertex).add(fromVertex);
        }

        //DFS
        for(int i=1; i<=vertexCount; i++){
            Collections.sort(graph.get(i), Collections.reverseOrder());
        }

        dfsRoute.push(startVertexNum);  
        while(!dfsRoute.isEmpty()){
            currentVertex= dfsRoute.pop();
            if(!isVisitedDfs[currentVertex]){
                isVisitedDfs[currentVertex]=true;
                result.append(Integer.toString(currentVertex)+" ");
            } 
            for(int i=0; i<graph.get(currentVertex).size(); i++){
                if(!isVisitedDfs[graph.get(currentVertex).get(i)]){
                    dfsRoute.add(graph.get(currentVertex).get(i));
                }
            }
        }
        System.out.println(result);
        result.delete(0, result.length());
        
        //BFS
        for(int i=1; i<=vertexCount; i++){
            Collections.sort(graph.get(i));
        }

        bfsRoute.add(startVertexNum);
        while(!bfsRoute.isEmpty()){
            currentVertex= bfsRoute.poll();
            if(!isVisitedBfs[currentVertex]){
                isVisitedBfs[currentVertex]= true;
                result.append(Integer.toString(currentVertex)+" ");
            } 
            for(int i=0; i<graph.get(currentVertex).size(); i++){
                if(!isVisitedBfs[graph.get(currentVertex).get(i)]){
                    bfsRoute.add(graph.get(currentVertex).get(i));
                }
            }
        }
        System.out.println(result);
    }
}