[백준1260번] DFS와 BFS

---

간단하게,

깊이우선탐색(DFS) 는 한 노드의 관해서 깊게 들어가면 된다. 따라서 한 노드를 방문했었는지를 기록하며 그 노드와 연결된 노드를 기준으로 다시 DFS메소드를 호출하면 된다.

 

너비우선탐색(BFS)는 한 노드에서 연결된 모든 노드를 방문하는 것이므로 큐를 이용하여 큐에서 빼낸 노드와 연결되며 방문하지 않은 모든 노드를 큐에 넣고 큐가 빌때까지 반복해주면 된다.

 

코드

package baekjoon;

import java.util.*;

public class dfs_bfs {

    public static boolean[] check;
    public static ArrayList<Integer> list[];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int start = scan.nextInt();

         list = new ArrayList[n+1];

        for(int i = 1;i<n+1;i++){
            list[i] = new ArrayList<Integer>();
        }

        for(int i = 0; i<m;i++){
            int a = scan.nextInt();
            int b = scan.nextInt();

            list[a].add(b);
            list[b].add(a);
        }
        for(int i = 1; i<n+1;i++){
            Collections.sort(list[i]);
        }

        check = new boolean[n+1];
        dfs(start);
        System.out.println();

        check = new boolean[n+1];
        bfs(start);

        scan.close();
    }

    public static void dfs(int cur){
        if(check[cur]){
            return;
        }
        check[cur] = true;
        System.out.print(cur + " ");
        for(int i : list[cur]){
            if(!check[i]){
                dfs(i);
            }
        }
    }

    public static void bfs(int cur){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(cur);
        check[cur] = true;

        while(!queue.isEmpty()){
            int a = queue.poll();
            System.out.print(a + " ");
            for(int i : list[a]){
                if(!check[i]){
                    check[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

- 노드가 1에서부터 시작하므로 나는 리스트를 만들더라도 1~n+1의 크기만큼 사용할 것이다.

- 연결리스트로 구현한 것으로 특정갑의 숫자들을 넣어주는 방법이다 ex) 1번에 2,3,4가 들어간다

- 동시에 여러 노드를 갈 수  있는 경우에는 작은수로 가라고 했으므로 sort를 한번 해준다.

- 출력은 각 메소드에서 직접해줄 것이므로 main안에서는 dfs와 bfs메소드 호출만 해주고 그 사이에 줄만 바꿔준다.

- dfs메소드 안에서는 현재지점을 기준으로 이미 방문했으면 return해주고 아니면 방문했다로 바꿔주고 현재값을 출력한다. 또한 list를 반복하며 그 안에 값을 꺼내주고 그 값이 방문하지 않았다면 그 값으로 dfs를 호출한다.

- 위에서 설명했듯이 bfs에는 큐가 필요하다. 현재값을 큐에 넣고 true로 바꿔준다

- 큐가 비어질 때까지 반복하는데 a에 큐의 맨 앞의 값을 빼주고 그 값을 출력한다. a의 값으로 list의 값들을 갖고 방문안했으면 방문한걸로 바꿔주고 큐에 넣어준다.

 

결과값

노드의 개수 4

간선의 개수 5

시작점 1

 

1 2 4 3 => 깊이우선탐색

1 2 3 4 => 너비우선탐색