[Java] DFS, BFS

DFS(깊이 우선 탐색, Depth-First Search)

루트노드(혹은 다른 임의의 노드)에서 다음 분기(Branch)로 넘어가기 전에, 해당 분기(Branch)를 모두 탐색 하는 방법

탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다.

 

특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택으로 구현)

->조합에서 뽑고, 재귀적으로 호출하고, 뽑은거 취소하는것처럼 , 자기 자신을 호출함으로서 해당 수를 뽑은 경우의 모든경우를 탐색한다.

 

2.그래프탐색인 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. ( 검사하지않을경우 무한루프에 빠질수 있다.)  ex) visited[index]  = true ,  if(!visited[index])     -> 일반 조합에서 중복뽑기를 방지하기위해 방문배열을 쓰는것처럼

 

3. 미로를 탐색할때 , 해당 분기에서 갈 수 있을때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

 

4. 모든 노드를 방문하고자 할때, 이 방법을 선택한다 ( 모든 경우를 살펴보고 싶지않다면 값이 아닌게 확실한 어떤 조건에서는 백트래킹하여 다른 분기(브런치)를 살펴보게해서 모든 조건을 살펴보지않도록한다. -> 연산 횟수가 줄어든다 )

 

5. 너비우선탐색(BFS)에 비해서 느리다.

 

과정

 

DFS 예시

다음과 그래프가 있다고할때

dfs 노드 탐색 순서는 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5

 

재귀를 이용한 구현

public class prac {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static boolean[] visited = new boolean[8 + 1]; // 인덱스를 1부터 사용하기 위해
    static int[][] graph = {{},
        {2, 3, 8},
        {1, 7},
        {1, 4, 5},
        {3, 5},
        {3, 4},
        {7},
        {2, 6, 8},
        {1, 7}};
    public static void main(String[] args) throws IOException {
        solve();

        bw.flush();
        bw.close();

    }

    static void solve() throws IOException {
        dfs(1); // 시작 노드는 1부터
    }

    static void dfs(int nodeIndex) {
        visited[nodeIndex] = true; //해당 노드를 방문처리하고
        System.out.print(nodeIndex +" ");

        //그 노드의 인접노드중 방문하지않은 노드를 다시 dfs 처리한다.
        for (int node : graph[nodeIndex]) {
            if (!visited[node]) {
                dfs(node);
            }
        }
    }
}

DFS 팁.

노드(정점)의 간선 정보를 저장할때는 리스트배열을 사용한다.   

ArrayList<Integer>[] graph  = new ArrayList[n+1];

정점갯수 +1 개를 해서 1번~n번 노드로 인덱스를 이용하는게 편하다.

 

반드시

배열요소를 초기화해 줘야한다. 리스트이니까.

for (int a = 1; a <= n; a++) {
    graph[a] = new ArrayList<>();
}

 

간선정보를 저장할때 무방향 그래프 or 양방향 그래프라면 노드 각각에 저장해준다.

for (int i = 0; i < m; i++) {
    input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    graph[input[0]].add(input[1]);
    graph[input[1]].add(input[0]);
}

 

 

예제

https://keeeeeepgoing.tistory.com/133

DFS는 최단경로찾기에 적합하지않다.

dfs는 모든경우에 대해 끝까지 살펴본후 최단경로였는지 체크한다.

 

BFS는 이동할수 있는 타일에 이전 이동횟수 +1 를 메모해가며 나아가므로 목적지에 타일에는 가장 적은 횟수가 적힌다.

트리구조에서 레벨마다 탐색하고 다음 레벨로 넘어가는것처럼 목적지에는 그 타일이 속한 레벨이 메모된다.

 

 

 

 

 

 

 

BFS(Breadth First Search), 너비 우선탐색

가까운 노드부터 탐색하는 알고리즘이다.

 

BFS는 최단경로(미로길찾기)와 같을때 사용하면 좋다.

특징

선입선출 방식인 큐 자료구조를 이용하는것이 정석이다.

 

인접한 노드를 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저들어온 것이 먼저 나가면서 주변 노드부터 탐색하게 된다.

1. BFS는 재귀적으로 동작하지않는다.

 

2. dfs와 똑같이 해당 노드를 방문했는지 체크해야한다. 방문배열을 사용해서

 

3. 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문하는 순회방법이다.

 

4. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을때 이 방법을 사용한다.

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A와 B사이에 존재하는 경로를 찾는 경우

dfs를 사용한다면 -> 모든 친구 관계를 다 살펴봐야할 수도 있다.

bfs를 사용한다면 -> a와 가까운관계(인접노드)부터 탐색한다.

 

과정

깊이가 1인 모든 노드를 방문하고 나서, 그다음에 깊이가 2인 모든 노드를, 그 다음엔 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할곳이 없으면 탐색을 마친다.

 

1. 시작정점(노드)를 큐에 넣고 시작한다.

 

2. 큐에 있는 노드를 하나 빼고 해당 노드의 인접노드를 전부 큐에 집어넣는다. 넣으면서 방문처리를 해준다(해당 인접노드가 다른 노드의 인접노드일 수도 있으므로 , 큐에 인접노드 추가할때 중복이 되지않으려면 어차피 방문할 인접노드는 방문처리를 해둬야한다)

 

3. (5) 번 그림을 보면 0번 노드의 모든 인접노드인 1,2,4가 큐에 들어간것을 확인할 수 있다.

 

4. 계속 큐에서 하나씩 뺴고, 인접노드 찾아서 방문하지않은거면 큐에넣고를 반복하다가 큐가 비게되면 방문할 노드가없다는것이므로 탐색을 종료한다.

-> 탐색 순서는 (큐에 들어간 순서 == 큐에서 나온 순서)이다.(poll)

다음과 같은 그래프를 BFS한다고 하면

노드의 탐색순서(큐에 들어간 순서)는 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

 

큐를 이용한 BFS 구현

public class prac {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static boolean[] visited = new boolean[8 + 1]; // 인덱스를 1부터 사용하기 위해
    static int[][] graph = {{},
        {2, 3, 8},
        {1, 7},
        {1, 4, 5},
        {3, 5},
        {3, 4},
        {7},
        {2, 6, 8},
        {1, 7}};
    public static void main(String[] args) throws IOException {
        solve();

        bw.flush();
        bw.close();

    }

    static void solve() throws IOException {
        bfs();
    }

    static void bfs() throws IOException{
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); // 시작 노드를 넣어준다.
        visited[1] = true;//시작 노드를 방문처리한다.

        while (!queue.isEmpty()) { //큐가 빌때까지 반복한다.
            int currentNodeIndex = queue.poll();
            bw.write(currentNodeIndex+" "); //뽑은 노드를 출력한다 ( 탐색순서)
            for (int node : graph[currentNodeIndex]) { //해당 노드의 인접노드를 다시 큐에 담는다.
                if (!visited[node]) { //방문하지 않았던 노드라면(큐에없는 노드라면)
                    queue.add(node); // 큐에 추가해준다.
                    visited[node] = true; //방문 처리해준다
                }
            }
        }

    }
}

 

 

 

·  앞서 DFS와 BFS를 설명하는 데 전형적인 그래프 그림을 이용했다.

   1차원 배열이나 2차원 배열 또한 그래프 형태로 생각하면 수월하게 문제를 풀 수 있다.

 

·  예를 들어 게임 맵이 3 x 3 형태의 2차원 배열이고 각 데이터를 좌표라고 생각해보자.

   이때 각 표로 상하좌우로만 이동할 수 있다면, 모든 좌표의 형태를 다음처럼 그래프의 형태로 바꿔서 생각할 수 있다.

 

코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 이렇게 그래프 형태로 바꿔서 생각하자.

풀이 방법을 더 쉽게 떠올릴 수 있다.

 

 

 

static void bfs() throws IOException {

    Queue<Integer> q = new LinkedList<>();
    q.add(start);
    visited[start] = true;

    while (!q.isEmpty()) {
        int nextNode = q.poll();

        for (int nearNode : graph[nextNode]) {
            if (!visited[nearNode]) {
                q.add(nearNode);
                visited[nearNode] = true; //이미 큐에 들어있는 노드를 다른노드의 인접노드를 살펴보다가 또 넣을수있으므로 큐에있는건 일단 방문처리한다.
            }
        }

    }

}

 

BFS를 이용해서 최단경로,최소이동횟수 구할때

기본 규칙

체스판의 범위를 넘는지 체크해줘야하고, 최소 이동이므로 이미 방문했던 위치는 큐에 넣지않는다.
나이트가 이동하는 규칙은 따로 배열로 저장해서 사용한다.
체스판 각각의 좌표에는 해당 위치를 이동할때 최소 이동횟수가 저장된다, 방문했는지 체크할 방문배열도 생성한다.

2가지 방법

bfs 최소이동문제 구현의 두가지방법
1. boolean 방문배열을 이용하여 방문체크하고 , 큐에는 이동하는 횟수를 같이 전달해줘서 , 목적지 도착하면 이동한 횟수를 출력하는 방법.
2. boolean 방문배열과 각 좌표에 이동횟수를 저장할 map 또는 result 배열을 이용하여 , bfs 돌고 난후 목적지 좌표에 저장된 값을 출력하는 방법.

2번은 모든 경우를 다돌아보고 난후 출력이라 1번에 비해 살짝 더 느리다.

 

2가지 방법 적용 예제

★백준/7562 나이트의 이동 /bfs

 

 

 

최단경로 예제

★백준/2178 미로탐색 /bfs

최단시간 예제 , 방문처리 , 범위 필터링 중요

 

★백준/1697 숨바꼭질 / bfs

 

가중치가 다를때 BFS 

큐에 넣는순서 or  방문처리 체크 

★★★ 백준/13549 숨바꼭질3 / bfs, 다익스트라 알고리즘 [미완]

 

그래프를 표현하는 2가지 방법 (행렬,리스트)

[Java]그래프의 표현

 

 

 

 

 

 

 

예제

백준/1012 유기농배추 / dfs, bfs

백준/2667 단지번호붙이기

백준/2606 바이러스 /dfs,bfs

 

 

출처,다 자세한정보

[Algorithm] DFS와 BFS란? 작동 방식과 구현 방법(with 자바)