[알고리즘] 백준 16930번 문제 (DFS, BFS)

 

www.acmicpc.net/problem/16930

16930번: 달리기

 

 

문제를 읽어보면, 시작점에서 도착점으로 이동하는 최소 시간을 구하라고한다. 이 문제를 읽자 마자 '아하 이건 시작점, 도착점, 최소 시간이라는 키워드를 사용하는걸로 봤을때 너비 우선 탐색(BFS) 문제구나!' 하고 알 수 있어야한다. 이제 이건 알겠고, 그럼 이제 너비 우선 탐색으로 어떻게 코딩을 할 수 있을까를 생각해본다.

 

 

깊이 우선 탐색 (DFS)

- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch) 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 미로를 탐색할 때 한 방향으로 갈 수 있을때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

- 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

- 사용하는 경우 : 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.

- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

- 깊이 우선 탐색의 특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

2. 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

3. 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.

 

 

넓이 우선 탐색 (BFS)

- 시작점과 도착점이 정해져 있고 이동하는 최소 시간을 묻는 문제가 출제된다.

 

 

그래프 탐색

- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

- 길찾기, 지하철 노선도, 어느 길로 가야 빨리 갈 수 있나에 대한 문제

- 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지

- 네트워크 탐색 A라는 회선에서 몇 개 연결 되어 있나

- A-B-C-D, E-F-G-U //2개 회선

 

완전이진트리

-tree 탐색 중에 full node가 아닌 node를 만날 경우

- 그 node 는 반드시 두 child node가 없거나 left node 만 존재해야 한다.

 

[정의] full node 라는 용어 : 이는 left, right child node가 모두 존재하는 노드를 칭한다.

 

완전 이진 트리라면 2가지 조건을 만족해야 하는데,

- TREE 탐색 중에 FULL NODE가 아닌 NODE 를 만날 경우

- 해당 NODE는 반드시 두 CHILD NODE가 없거나 LEFT NODE만 존재해야 한다.

- 그리고 그 이후에 탐색하게 되는 NODE 들은 모두 LEFT NODE 여야 한다.

 

 

 

---

 

미로찾는 문제에서 깊이 우선 탐색을 해본다고 하자. 세가지의 갈림길이 있는데 깊이 우선 탐색(DFS)은 깊이를 우선시 하기 때문에 한 길로만 일단 쭉 간다. 앞만 보고 그냥 계속 직진만 해야한다.

 

하지만 넓이 우선 탐색(BFS)의 경우에는 세가지의 갈림길이 있다면 사람 세명을 각각 길에 한명씩 보내서 동시에 세가지 길을 탐색하게 한다. 그렇기 때문에 빠른 길 찾기 문제의 로직을 짜야한다면 넓이 우선 탐색을 사용하는 것이 적절하다는 것이다.

 

---

 

 

 

 

---

 

구현 방법

package level4;
//https://www.acmicpc.net/problem/16930

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Algorithm13 {

    public static int solution() throws IOException {
        //1. 체육관 크기, 최대 이동 칸 결정
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        final int mazeY = Integer.parseInt(stringTokenizer.nextToken());
        final int mazeX = Integer.parseInt(stringTokenizer.nextToken());
        final int moveMAX = Integer.parseInt(stringTokenizer.nextToken());

        //2. 체육관 생성
        char[][] maze = new char[mazeY][mazeX+1];
        int[][] visit = new int[mazeY][mazeX+1];
        final char dot = '.';
        final char wall = '#';

        for (int i = 1; i < mazeY; i++) {
            String str = bufferedReader.readLine();
            for (int j = 1; j < mazeX; j++) {
                maze[i][j]=str.charAt(j-1);

            }
        }

        //3. 출발점, 도착점 결정
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        final int startY = Integer.parseInt(stringTokenizer.nextToken());
        final int startX = Integer.parseInt(stringTokenizer.nextToken());
        final int endY = Integer.parseInt(stringTokenizer.nextToken());
        final int endX = Integer.parseInt(stringTokenizer.nextToken());

        //4. 북동남서를 정의합니다.
        int[][] direction = {
                {-1, 0}, //북
                {0, 1},  //동
                {1, 0},  //남
                {0, -1}  //서
        };

        //5. 데크를 만듭니다.
        Deque deque = new ArrayDeque<>();

        //6. 출발점을 데크에 넣습니다.
        deque.add(new int[]{startY, startX});
        visit[startY][startX] = 0; // 방문체크. 출발지를 0으로 설정합니다.

        //7. 데크안에 있는 값이 모두 빠져나와서 값이 없을때까지 반복해줍니다.
        finish:
        while(!deque.isEmpty()) {
            int[] now = (int[]) deque.poll();
            int nowY = now[0]; //데크에 넣었던 첫번째 값은 startY 이고 두번째 값은 startX 값이다.
            int nowX = now[1]; // 따라서 이렇게 0번째, 1번째 값을 꺼내면 start 값을 알 수 있다.
            for (int i = 0; i < 4; i++) { //북동남서 방향으로 갈 수 있는 곳이 있는지 체크한다.
                for (int j = 1; j < moveMAX; j++) {
                    int nY = nowY + direction[i][0]; // {-1, 0} 북
                    int nX = nowX + direction[i][1]; // {0, 1} 동
                    if (nY > 0 && nX > 0 && nX <= mazeX && nY <= mazeY && maze[nY][nX] == dot) {
                        if (visit[nY][nX] == 0) {
                            visit[nY][nX] = visit[nowY][nowX] + 1; // 가중치를 넣어줍니다.
                            if (nY == endY && nX == endX) break finish;
                        } else if (visit[nY][nX] <= visit[nowY][nowX]) {
                            break;
                        } else {
                            break;
                        }
                    }
                }
            }
        }
            System.out.println(visit[endY][endX] == 0 ? -1 : visit[endY][endX]);
        return visit[endY][endX] == 0 ? -1 : visit[endY][endX];
    }//solution end

    public static void main(String[] args) throws IOException {
        Algorithm13 algorithm13 = new Algorithm13();
        algorithm13.solution();
    }
}//class end