[알고리즘] 탐색 - DFS, BFS, 이진 탐색

|  탐색이란?

주어진 데이터들 중에서 원하는 데이터를 찾아내는 알고리즘

 

|  탐색의 종류

	언제?	특징	시간복잡도
DFS(깊이 우선 탐색)	그래프의 모든 노드를 탐색하고자 할 때	- 재귀 또는 스택을 통해 구현 - 트리의 pre-order, in-order, post-order 순회 모두 DFS이다.	* 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2)
BFS(너비 우선 탐색)	그래프의 가까운 지점부터 탐색하고자 할 때	- 큐를 통해서 구현 - 트리의 level-order 가 BFS이다.	* 인접 행렬 : O(V+E) * 인접 리스트 : O(V^2)
이진 탐색

* DFS, BFS 모두 간선의 갯수가 적을 때에, 인접 리스트를 쓰는게 유리하다.

 

1. DFS (깊이 우선 탐색)

DFS란, 루트에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

[출처] https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

- 참조한 블로그에서는 미로를 탐색하는 것을 이야기했는데, 미로의 여러 갈랫길 중 첫번째 길만 쫒아가다가 다시 돌아와(backtracking) 방문하지 않은 곳을 탐색하여, 결국 모든 곳을 가는 것을 DFS라고 했다.

- 하나의 노드 A와 인접한 노드가 B, C가 있다고 할 때 먼저 B의 분기(인접한 노드들)를 모두 마쳐야만, C를 갈 수 있다.

- 트리의 level-order을 제외한 나머지 순회들과의 차이점은 어떤 노드를 방문했는지를 방문 배열을 통해 검사한다는 것.

 

출처:위키백과

(1) 구현 

스택	재귀 (순환 호출)
1. 시작 노드 정한 후, 사용할 자료구조 초기화 - 인접 리스트로 그래프 표현 - 방문 배열 초기화 후 시작지점 true 표시 - 시작 노드를 스택에 삽입 2. 스택에서 노드 꺼낸 후 인접 노드 다시 삽입하며 방문 체크 3. 스택에 값이 없을 때까지 2를 반복	1. 사용할 자료구조 초기화 - 인접리스트로 그래프 표현 - 방문 배열 초기화 2. 루트 노드(=시작 노드)를 방문하여 방문 체크 3. 인접한 노드들 중 방문하지 않은 곳을 방문 4. 방문할 노드들이 없을 때까지 3를 반복

- 백준의 아래 문제를 통해 한 번 구현해보았다.

[1] 먼저 자료구조를 초기화한다. : 정점/간선 갯수나, 인접리스트, 방문배열은 전역으로 빼주었다.

public class Ex11724 {

    static int N;
    static int M;
    static List<List<Integer>> graph;
    static boolean[] visited;
    static int cnt;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 인접 리스트 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        // 방문 배열 초기화
        visited = new boolean[N + 1];

        cnt = 0;
    }
}

[2] 문제에서 요구하는 연결망의 갯수 구하는 코드를 넣는다.

- 이 문제는 프로그래머스의 '네트워크' 문제와도 유사했는데, 분리된 연결망을 구하는 문제였다.

> 분기를 확인하기 위한 코드

// 2. dfs
for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
        dfs_stack(i);
        cnt++;
    }
}

System.out.println(cnt);

> 예외 상황 : 노드가 하나밖에 없고 간선이 없는 경우 - 네트웍은 하나다.

// 노드가 하나밖에 없고 간선이 없어도 네트웍은 하나로 치부
if (N == 1 && M == 0) {
    System.out.println(1);
    return;
}

[3] 본격적인 dfs를 짜기

 

[3-1] 재귀 방식의 dfs

public static void dfs(int root) {

    // 루트 방문 체크
    visited[root] = true;

    // 인접한 노드들 중 방문하지 않은 곳을 방문
    for (int i = 0; i < graph.get(root).size(); i++) {

        int adjNode = graph.get(root).get(i);

        if (!visited[adjNode]) {
            dfs(adjNode);
        }
    }

}

 

[3-2] 스택 방식의 dfs

public static void dfs_stack(int start) {

    Stack<Integer> stack = new Stack<>();
    visited[start] = true;
    stack.push(start);

    while (!stack.isEmpty()) {
        int curNode = stack.pop();

        for (int i = 0; i < graph.get(curNode).size(); i++) {
            int adjNode = graph.get(curNode).get(i);

            if (!visited[adjNode]) {
                stack.push(adjNode);
                visited[adjNode] = true;
            }
        }
    }
}

[ 전체 코드 - 더보기 ]

package graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;


public class Ex11724 {

    static int N;
    static int M;
    static List<List<Integer>> graph;
    static boolean[] visited;

    static int cnt;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        if (N == 1 && M == 0) {
            System.out.println(1);
            return;
        }

        // 1. 시작 노드를 정한 후 사용할 자료구조 초기화
        // 인접 리스트 그래프 초기화
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        // 방문 배열 초기화
        visited = new boolean[N + 1];

        cnt = 0;

        // 2. dfs
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs_stack(i);
                cnt++;
            }
        }

        System.out.println(cnt);
    }

    public static void dfs(int root) {

        // 루트 방문 체크
        visited[root] = true;

        // 인접한 노드들 중 방문하지 않은 곳을 방문
        for (int i = 0; i < graph.get(root).size(); i++) {

            int adjNode = graph.get(root).get(i);

            if (!visited[adjNode]) {
                dfs(adjNode);
            }
        }

    }

    public static void dfs_stack(int start) {

        Stack<Integer> stack = new Stack<>();
        visited[start] = true;
        stack.push(start);

        while (!stack.isEmpty()) {
            int curNode = stack.pop();

            for (int i = 0; i < graph.get(curNode).size(); i++) {
                int adjNode = graph.get(curNode).get(i);

                if (!visited[adjNode]) {
                    stack.push(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

}

 

(2) 시간 복잡도

- DFS는 그래프의 정점의 수(V)와 간선의 수(E)를 통해 시간 복잡도를 표현하는데,

- 인접 행렬을 사용하는 경우, 행으로는 전체 정점(V)을, 열로는 인접한 정점과의 연결 여부(E)를 확인하므로, 

  -- O(V^2) 의 시간 복잡도를 가진다.

- 인접 리스트를 사용하는 경우, 각 정점(V)을 방문한 후, 인접 노드를 따라 하나씩 탐색하기 때문에,

  -- O(V + E)의 시간 복잡도를 가진다.

- 그래프를 완전 탐색할 때에는 따라서, 간선이 적을 때에 인접 리스트를 사용하는 것이 좋다.

 

 

2. BFS (너비 우선 탐색)

bfs란, 루트에서 시작해서 인접한 노드를 먼저 탐색하는 방법

[출처] https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

- DFS의 경우, 깊이 있게 탐색했다면, BFS는 가까운 지점을 먼저 탐색하는 "넓은" 탐색이다.

- 참고한 블로그에서는, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때에 이 방법을 쓴다고 했다.

- BFS를 활용한 알고리즘이 바로 최단 경로를 구하는 다익스트라였다. 

  * BFS와 차이점이 있다면, 다익스트라는 DP를 사용한다는 점..

https://why-dev.tistory.com/247?category=958869 

[알고리즘] 최단 경로 구하기 - 1. 다익스트라

- BFS는 구현 방법을 정리하기 보다, 문제를 보면서 얘기해보려고 한다.

- 아래는, 프로그래머스의 게임 맵 최단 거리를 구하는 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/1844#

프로그래머스

 

(1) 코드

: 아래를 보면 알 수 있듯이, 게임 최단 거리를 구하는 문제는 BFS로 풀어야 했는데,

: 그 이유는 사방위로 움직여서 갈 수 있는 경로 중 도착지에 가까운 경로를 선택하려면,

  깊이있는 탐색보다는 너비 탐색을 통해서 사방위중 도착지에 가까운 방향 (아래로, 우측으로)으로 먼저 탐색을 하고,

  탐색한 횟수에 대해 저장하며 나아가야 했기 때문이다.

: DFS로 풀게될 경우에는 이런 탐색 횟수를 저장하며 갈 때 너무 많은 시간이 소요된다. 

  (왜냐면 깊이 탐색 후, 다시 제자리로 돌아와서 또 다른 갈래로 깊이 탐색 후, 또 다른 갈래로 깊이 탐색을 해야해서...)

: 그렇기에 그래프 최단 경로를 구할 때에도 BFS를 응용한 다익스트라를 사용한다.

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    class Node {
        int r;
        int c;
        int cnt;

        public Node(int x, int y, int cnt) {
            this.r = x;
            this.c = y;
            this.cnt = cnt;
        }
    }

    int[][] maps;
    int[][] dir = {{0, 1},{1, 0},{0, -1},{-1, 0}};

    public int solution(int[][] maps) {
        this.maps = maps;

        return bfs(maps.length, maps[0].length);
    }

    public int bfs(int r, int c){

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, 0, 1));
        maps[0][0] = 0;

        while (!q.isEmpty()) {
            Node cur = q.poll();

            if (cur.r == r - 1 && cur.c == c - 1) {
                return cur.cnt;
            }

            for (int[] d : dir) {
                int newR = cur.r + d[0];
                int newC = cur.c + d[1];

                if (newR >= 0 && newC >= 0 && newR < r && newC < c) {
                    if (maps[newR][newC] == 1) {
                        maps[newR][newC] = 0;
                        q.add(new Node(newR, newC, cur.cnt + 1));
                    }
                }
            }
        }

        return -1;
    }
}

 

 

[ 참고 및 출처 ]

부트캠프 수업 내용 정리

[Do it 알고리즘 코딩 테스트 - 자바 편]

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

프로그래머스