[백준/1260/Java] DFS와 BFS

BFS와 DFS

시간	제한메모리	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	163706	57810	34044	34.656%

 

 

문제

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

 

 

입력

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

 

 

출력

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

 

예제 입력 1

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

 

예제 출력 1

1 2 4 3
1 2 3 4

 

예제 입력 2

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

 

예제 출력 2

3 1 2 5 4
3 1 4 2 5

 

예제 입력 3

1000 1 1000
999 1000

 

예제 출력 3

1000 999
1000 999

 

 

 

 

풀이

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

public class Q1260 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();




        int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        final int POINT_COUNT = inputs[0]; //정점의 개수
        final int LINE_COUNT = inputs[1]; //간선의 개수
        final int START_POINT = inputs[2]; //탐색을 시작할 정점의 번호





        ArrayList<ArrayList<Integer>> map = makeAndSetMap(br, POINT_COUNT, LINE_COUNT);



        IntStream.rangeClosed(0, POINT_COUNT).forEach(i -> map.get(i).sort(Comparator.naturalOrder()));




        Graph graph = Graph.from(map);




        graph.dfs(START_POINT, sb);

        graph.resetVisiting();

        sb.append("\n");

        graph.bfs(START_POINT, sb);

        System.out.println(sb.toString());
    }



    private static ArrayList<ArrayList<Integer>> makeAndSetMap(BufferedReader br, int POINT_COUNT, int LINE_COUNT) throws IOException {
        ArrayList<ArrayList<Integer>> map = new ArrayList<>();

        IntStream.rangeClosed(0, POINT_COUNT).forEach(i -> map.add(new ArrayList<>()));

        for (int i = 0; i< LINE_COUNT; i ++){
            int[] lines = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = lines[0];
            int end = lines[1];

            map.get(start).add(end);//양방향이므로
            map.get(end).add(start);
        }
        return map;
    }
}



class Graph{

    private ArrayList<ArrayList<Integer>> map = new ArrayList<>();
    private boolean[] visited;

    private Graph(ArrayList<ArrayList<Integer>> map){
        this.map = map;
        visited = new boolean[map.size()];
    }


    public static Graph from(ArrayList<ArrayList<Integer>> map){
        return new Graph(map);
    }
    public void resetVisiting(){
        visited = new boolean[map.size()];
    }




    public String bfs(int startPoint, StringBuilder sb){
        //StringBuilder -> 단일 스레드에서 성능 가장 좋음
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(startPoint);
        visited[startPoint] = true;


        while (!deque.isEmpty()){
            Integer currentPoint = deque.poll();
            sb.append(currentPoint + " ");

            IntStream.range(0, map.get(currentPoint).size())
                    .forEach(i -> checkAndEnque(map.get(currentPoint).get(i), deque));


        }
        return sb.toString();
    }


    private void checkAndEnque(int endPoint, Deque<Integer> deque) {
        if (visited[endPoint]) return;

        deque.offer(endPoint);
        visited[endPoint] = true;
    }






    public String dfs(int startPoint, StringBuilder sb){
        if(visited[startPoint]) return null;

        visited[startPoint] = true;
        sb.append(startPoint + " ");

        IntStream.range(0, map.get(startPoint).size()).forEach(i -> {
            checkAndDfs(map.get(startPoint).get(i), sb);
        });

        return sb.toString();
    }

    private void checkAndDfs(int endPoint, StringBuilder sb) {
        if(visited[endPoint]) return;
        dfs(endPoint, sb);
    }
}