[백준 1260번] DFS와 BFS (java) + 정렬하기

DFS와 BFS 

 

문제

그래프를 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

---

필수로 알고있어야 하는 선수지식

DFS와 BFS의 개념과 구현방법

[Java] DFS , BFS 개념, 연결리스트로 구현하기

DFS은 스택 또는 재귀, BFS는 큐로 구현하는 것입니다. 이 아이디어만 가지고 문제에 적합하게 완전히 새로 구현해야 합니다.

---

전체 코드

이 문제에서는 노드class를 따로 생성하지 않고, 번호(인덱스)로 대체할수 있기 때문에 NODE 객체없이 구현했습니다.

DFS의 경우는, 재귀호출을 이용해 구현했습니다.

LinkedList로 구현하는 것이 일반적인데, linkedlist는 추가 삭제가 빠르지만 탐색이 느리고, ArrayList는 추가 삭제가 느리지만, 탐색은 일반 배열과 같이 빠릅니다.

이 문제에서는 adjacent(자식노드 리스트)를 초기에만 변경하고 이후론 변경하지 않으므로, 시간 복잡도가 적은 ArrayList를 활용했습니다.

- 인접행렬말고 리스트를 이용하는 이유 => 행렬을 이용하면 공간 복잡도가 증가해서 채점 실패합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;

public class Silver_1260{
    // Inner Class needs static
    static class Graph {
        boolean[] visited;
        ArrayList<Integer>[] adjacents;
        Graph(int size){
            this.visited = new boolean[size+1];
            this.adjacents = new ArrayList[size+1];
            for (int i = 1; i <= size ; i++) {
                adjacents[i] = new ArrayList<Integer>();
            }
        }
        void addEdge(int n1 , int n2){
            if(!adjacents[n1].contains(n2)){
                adjacents[n1].add(n2);
            }
            if(!adjacents[n2].contains(n1)){
                adjacents[n2].add(n1);
            }
        }

        // Search Fuctions (Dfs & Bfs) //

        //DFS
        public void dfs() {
            dfs(1);
        }
        public void dfs(int index) {
            visited[index] = true;
            visit(index);
            Collections.sort(adjacents[index]);
            for (Integer node : adjacents[index]) {
                if (visited[node]==false) {
                    dfs(node);
                }
            }
        }
        
        //BFS
        public void bfs() {
            bfs(1);
        }
        public void bfs(int index) {
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(index);
            visited[index] = true;
            while (!queue.isEmpty()) {
                int parent = queue.poll();
                visit(parent);
                Collections.sort(adjacents[index]);
                for (Integer node : adjacents[parent]) {
                    if (visited[node]==false) {
                        queue.add(node);
                        visited[node] = true;
                    }
                }
            }
        }
        public void InitMarked(){
            for (int i = 1; i < visited.length ; i++) {
                visited[i] = false;
            }
        }
        public void visit(int index) {
            System.out.print(index+" ");
        }
    }//Graph


    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int numberOfNodes = Integer.parseInt(st.nextToken());
        int numberOfEdges = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        Graph graph = new Graph(numberOfNodes);
        for (int i = 0; i < numberOfEdges; i++) {
            st = new StringTokenizer(br.readLine());
            graph.addEdge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        br.close();
        graph.dfs(start);
        System.out.println();
        // 그래프를 방문한 내용 초기화
        graph.InitMarked();
        graph.bfs(start);
    }
}

---

리스트 정렬하기

이 문제에서는 자식노드들이 있으면 오름차순으로 방문하라고 했습니다.

그런데 그래프들의 정점을 오름차순으로 입력되어있지 않기 때문에 정렬을 해야합니다.

만약 2의 인접노드리스트(adjacent)가 {5, 3, 1, 4} 이면, {1, 3, 4, 5}로 정렬하고 차례대로 탐색해야 합니다.

 

1) 배열일 경우 정렬

int arr[] = {4,23,33,15,17,19};
Arrays.sort(arr); // 오름차순
Arrays.sort(arr, Collections.reverseOrder()); // 내림차순

Arrays 클래스를 이용해서 정렬할수 있습니다. 근데 이건 배열에만 적용되고, ArrayList, LinkedList처럼 리스트를 정렬하려면 Collection 클래스를 이용해합니다.

 

2) 리스트 객체 정렬

ArrayList, LinkedList처럼 리스트는 아래와 같이 정렬하면 됩니다.

// 대상 리스트 => list
Collections.sort(list);// 오름차순
Arrays.sort(list , Collections.reverseOrder()); // 내림차순

 

dfs의 경우 아래와 같이 정렬후, 재귀를 이용해 탐색했습니다.

Collections.sort(adjacents[index]);
            for (Integer node : adjacents[index]) {
                if (visited[node]==false) {
                    dfs(node);
                }