[백준] 1260 : DFS와 BFS (DFS, BFS 알고리즘) - JAVA

백준 알고리즘 분류 (깊이 우선 탐색)

https://www.acmicpc.net/problem/1260

 

 

# 문제

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

 

 

# 예제

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

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

 

출력

1 2 4 3
1 2 3 4

 

 

 

# 필요개념

이 문제는 dfs와 bfs를 구현하는 문제이기 때문에, 어떤식으로 구현해야 하는지 알고있어야 한다. 이론적인 부분은 요기에 간단하게 정리해두었다!

https://wanna-developer02.tistory.com/54

[알고리즘] CHAP 5. Backtracking Algorithm (백트래킹 알고리즘) - Monte Carlo Algo-

 

그래요 이론은 알겠는데요 .. 그래서 어떤식으로 구현해야 되는건데요

 

DFS

DFS는 자식노드를 부모노드삼아 계속계속 자식노드를 탐색하는 알고리즘이다. 그래서 재귀를 사용해준다. 

추가로, 방문한 노드를 다시 탐색할 필요가 없기 때문에 이를 판단하기 위해 방문여부를 담고있는 boolean배열을 사용한다.

dfs

BFS

BFS는 한 노드의 자식노드를 모두 돌고, 자식노드의 자식노드를 모두 도는 것을 반복한다. 그래서 한 노드만 먼저 파는 dfs랑은 방법이 다르다. 보통 모든 자식노드를 돈 후, 그중 먼저 방문한 자식노드의 자식노드를 다 도는 것을 반복한다.

그래서 ! 큐라는 자료구조를 사용한다. 큐에다가 자식노드를 모두 넣고, poll해서 그 자식노드를 모두 큐에 담는 걸 반복하는 것이다.

bfs

 

이 문제를 풀 때 dfs와 bfs를 모두 구현해야하고, 노드를 입력받을 때 그냥 받는 게 아니라, 한 노드와 연결되어있는 노드를 알 수 있게끔 입력받는다. 그래서 노드가 7개라면 7 * 7 크기인 이차원배열을 만들어 담았었다.

 

예를 들면, 1번노드와 2,3,4번 노드가 직접 연결되고, 2노드와 5노드가 직접 연결된 구조라면,

[[2,3,4],[5],[],[],[2]] 이런식으로 담으려고 했다! 즉, 한 기준노드를 인덱스로 설정해 직접 연결된 노드를 같은 행에 담는 식으로 말이다.

 

그런데 이렇게 하니까 메모리를 꽤 많이 먹기도 하고, 인덱스 관리도 힘들어서 List 배열을 사용했다.

static ArrayList<Integer>[] store;

 

이렇게 배열에 리스트를 넣어두면, 인덱스 관리도 필요없다 ! bfs와 dfs 메소드에서도 접근해야 하기 때문에, 클래스 아래에 static을 붙여 선언해두고, 생성은 main함수 안에서 했다.

store = new ArrayList[n]; // arraylist배열 생성

 

# Code

코드는 아래와 같다.

import java.util.*;
import java.io.*;
public class Main {
    static ArrayList<Integer>[] store;
    static int n;
    static boolean[] isVisitDfs; // 여기서 = new isVisitDfs[n] 으로 하면 n이 0으로 초기화 된 상태에서 생성되기 때문에 n을 받은 후 main 안에서 배열 생성해야함
    static boolean[] isVisitBfs;
    static StringBuilder sb = new StringBuilder();
    static Queue<Integer> queue = new ArrayDeque<>();

    public static void main(String[] args) throws IOException{
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // number of node
        int m = Integer.parseInt(st.nextToken()); // number of line
        int start = Integer.parseInt(st.nextToken()); // start number

        store = new ArrayList[n]; // arraylist배열 생성
        isVisitDfs = new boolean[n];
        isVisitBfs = new boolean[n];

        for (int i = 0 ; i < n ; i++) {
            store[i] = new ArrayList<>();
        }
        for (int i = 0 ; i < m ; i++) {
            st = new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            store[parent - 1].add(child);
            store[child - 1].add(parent);
        }
        for (int i = 0 ; i < n ; i++) {
            Collections.sort(store[i]);
        }
        dfs(start);
        sb.append("\n");
        bfs(start);
        System.out.println(sb.toString());

        
    }

    public static void dfs(int s) {
        isVisitDfs[s - 1] = true;
        sb.append(s).append(" ");
        for (int i : store[s - 1]) {
            if (!isVisitDfs[i - 1]) {
                dfs(i);
            }
        }
    } 



    public static void bfs(int s) {
        isVisitBfs[s - 1] = true;
        queue.add(s);
        while(!queue.isEmpty()) {
            for (int i : store[queue.peek() - 1]) {
                if (!isVisitBfs[i - 1]) {
                    queue.add(i);
                    isVisitBfs[i - 1] = true; 
                }
            }
            sb.append(queue.peek()).append(" ");
            queue.poll();
        }
    } 
}

 

# 결과