[백준 - 2512] 나이트 이동 - Java(Feat. DFS vs BFS)

문제 설명

 

7562번: 나이트의 이동

 

 

풀이 회고 : DFS와 BFS 차이에 대한 고찰

해당 문제에서는 체스판 위에 "나이트"의 "현재 위치"가 주어졌을 때 "특정(목표) 위치"로 갈 수 있는 최소 이동 횟수를 요구하고 있습니다. 즉 특정 지점에서 출발하여 "나이트의 이동 방식"에 맞춰 체스판(그래프) 위 각 좌표(노드)들을 탐색하면서 목표 위치를 찾아내야 합니다. 이때 최소 이동 횟수를 구해야 하므로 각 노드들을 이동할 때마다 이동 횟수를 1씩 더해주어야 합니다. 이러한 탐색 방법에는 DFS(깊이 우선 탐색)를 이용한 방법과 BFS(너비 우선 탐색)을 이용한 방법이 있습니다.

 

BFS(너비 우선 탐색)을 이용한 방법

이 문제는 BFS을 통해 해결할 수 있었습니다. 우선 소스 코드는 다음과 같습니다.

 

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

class Main {

    static int I, r, c;
    static int[] dx = {1, 1, -1, -1, 2, 2, -2, -2}, dy = {2, -2, 2, -2, 1, -1, 1, -1};
    static boolean[][] visited;

    static class Point {
        int x;
        int y;
        int result;

        public Point(int x, int y, int result) {
            this.x = x;
            this.y = y;
            this.result = result;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x, y;

        for (int i = 0; i < n; i++) {
            I = sc.nextInt();
            x = sc.nextInt();
            y = sc.nextInt();
            r = sc.nextInt();
            c = sc.nextInt();

            visited = new boolean[I][I];
            visited[x][y] = true;
            bfs(x, y);
        }
    }

    public static void bfs(int x, int y) {
        int nx, ny;

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y, 0));

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            if (point.x == r && point.y == c) {
                System.out.println(point.result);
                break;
            }

            for (int j = 0; j < 8; j++) {
                nx = point.x + dx[j];
                ny = point.y + dy[j];

                if ( nx < 0 || nx > I - 1 || ny < 0 || ny > I -1 ) {
                    continue;
                }

                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.add(new Point(nx, ny, point.result + 1));
                }
            }
        }
    }
}

 

우선 나이트의 위치와 이동 횟수를 저장하고 있는 Point 구조체를 별도로 선언해주었습니다. 이후 최초(현재) 위치를 담은 Point 구조체(이동 횟수 = 0)를 생성해준 후 이를 Queue에 add시켰습니다. 그 다음 현재 위치를 기준으로 이동할 수 있는 위치를 탐색하는데 나이트가 이동할 수 있는 위치는 총 8가지의 경우의 수입니다. 즉, Queue에 들어있는 노드들을 순차적으로 그리고 각각의 노드별 기준으로 이동할 수 있는 8가지 방향으로 탐색(for문 활용)을 하면서 목표 위치(R, C)에 도달할 때까지 확장하며 탐색을 진행합니다. 새로 이동한 위치에 대한 Point 객체는 다시 Queue에 add시켜 다음 탐색 순서가 올때까지 대기하도록 합니다. 이때 8가지의 방향을 나타내기 위해 정수형 배열 dx와 dy에 좌표들을 선언해주었습니다.

 

이때 중요한 것은 8가지 방향으로 확장해가며 탐색(너비 탐색)을 할 때 나이트 입장에서 이미 방문했던 체스판 좌표는 또 다시 방문할 필요가 없다는 사실입니다. 왜냐하면 이 문제는 목표 위치까지 도달할 수 있는 최소 이동 횟수를 요구하고 있는데, 방문 했던 곳을 한 번 더 방문하는 것은 낭비이기 때문입니다. 즉, 현재 위치에서 목표 위치로 가는 데에는 다양한 경로가 존재하겠지만 어느 경로든 특정 체스판 좌표를 중복해서 움직일 필요는 없습니다. (이미 방문했던 곳에 다시 방문한다고 해서 새로운 경로가 생기는 것이 아니기 때문!!) 즉, 방문했던 곳은 boolean형 배열 visited을 통해 방문 처리해주도록 합니다.

 

이렇게 나이트가 이동하다보면 체스판의 범위를 넘어가는 경우도 있을 것입니다. 이 경우에는 별도 방문 처리나 다음 탐색을 도모할 필요(Queue add)는 없으므로 그대로 다음 방향으로 탐색하도록 continue시킵니다.

 

지금까지의 상황을 그림으로 도식화해보면 다음과 같습니다. 

 

 

이런 식으로 현재 위치를 기준으로 8개의 방향으로 확장되어가는데, 이때 두드러지는 특징은 어느 하나의 경로가 다른 경로 보다 앞서 나가는 것이 아니라, 8개의 경로가 순차적으로 각각의 경로대로 한 칸씩 이동한 다음 모두 이동을 완료하면 다시 순차적으로(이 순서는 앞서 선언한 dx와 dy 좌표에 따라 결정됩니다.) 한 칸씩 이동한다는 점입니다. 즉, 현재 위치(노드)를 기준으로 자기 자신의 너비를 우선 탐색 즉, 우선적으로 간선으로 연결된 노드들을 순차적으로 모두 탐색하는 것입니다.

 

이런 식으로 확장해가며 너비를 탐색하다보면 목표 위치(R, C)에 도달하는 노드(Point 객체)가 발생할텐데 가장 먼저 탐색된 것에 대한 이동 횟수(result) 값이 문제에서 요구하는 최소 이동 횟수라고 볼 수 있을 것입니다. 따라서 해당 result 값을 출력한 이후 break를 통해 while문을 빠져 나오면 끝입니다.

 

 

DFS(깊이 우선 탐색)을 이용한 방법

사실 이 문제를 처음 접근했을 때는 DFS로 접근했었습니다. 하지만 결과는 "시간 초과"였습니다. 우선 DFS를 이용하여 문제에 접근했었던 소스 코드는 다음과 같았습니다.

 

import java.util.Scanner;

class Main {

    static int I, r, c;
    static double result = Double.POSITIVE_INFINITY;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x, y;
        boolean[][] visited;

        for (int i = 0; i < n; i++) {
            I = sc.nextInt();
            x = sc.nextInt();
            y = sc.nextInt();
            r = sc.nextInt();
            c = sc.nextInt();

            visited = new boolean[I][I];
            dfs(x, y, 0, visited);
            System.out.println((int) result);
            result = Double.POSITIVE_INFINITY;
        }
    }

    public static void dfs(int x, int y, int cnt, boolean[][] visited) {
        if (x < 0 || x > I - 1 || y < 0 || y > I - 1 || cnt > result || visited[x][y]) {
            return;
        }

        if (x == r && y == c) {
            result = cnt;
            return;
        }

        boolean[][] d = new boolean[I][I];
        for (int i = 0; i < I; i++) {
            System.arraycopy(visited[i], 0, d[i], 0, visited[0].length);
        }

        d[x][y] = true;
        cnt++;

        dfs(x + 2, y + 1, cnt, d);
        dfs(x + 2, y - 1, cnt, d);
        dfs(x - 2, y + 1, cnt, d);
        dfs(x - 2, y - 1, cnt, d);

        dfs(x + 1, y + 2, cnt, d);
        dfs(x + 1, y - 2, cnt, d);
        dfs(x - 1, y + 2, cnt, d);
        dfs(x - 1, y - 2, cnt, d);
    }
}

 

Queue를 이용하는 BFS와 달리 DFS는 재귀함수를 이용합니다. 또한 나이트의 8가지 방향을 정수형 배열 dx와 dy를 통해 나타내주었던 BFS와 달리 DFS에서는 8개의 재귀함수를 통해 각 방향을 나타내어 줍니다. 하지만 DFS에서 역시 이전에 방문했던 위치는 또 다시 방문할 필요는 없으므로 booleand형 배열 visited를 통해 방문 처리 해줍니다. (방문 처리 안 하면 특정 재귀함수간 싸이클이 생겨 무한 호출되면서 '스택오버플로우'가 발생합니다!!)

 

여기서 BFS와의 중요한 차이점이 발생하게 됩니다. BFS는 현재 나이트 위치에서 8가지의 방향으로 8개의 경로가 순차적으로 각각의 경로대로 한 칸씩 이동한 다음 모두 이동을 완료하면 다시 순차적으로 한 칸씩 이동했었습니다. 하지만 DFS는 특정 하나의 경로가 모두 다 이동을 마친 이후에 다른 경로가 남은 경로를 다 이동을 완료하는 식으로 탐색이 진행됩니다. 이를 도식화해보면 다음과 같습니다.

 

 

즉, DFS를 통해 탐색을 하다보면 하나의 경로가 이동을 하면서 방문 처리를 하는 것이 다른 경로가 이동하는데 지장을 줄 수 있는 것입니다. BFS의 경우에는 8개의 경로가 순차적으로 한칸씩 이동했습니다. 그리하여 BFS는 8개 중 특정 경로 중 하나가 이미 방문 처리 한 곳을 방문하여 무시되더라도 앞서 방문한 경로가 더 적은 횟수로 이동한 것을 의미하는 것이므로 문제에서 요구한 것을 충족시키기에 오히려 좋습니다. 하지만 DFS는 하나의 경로가 우선적으로 이동 횟수를 늘리면서 그리고 방문 처리하면서 탐색하는 과정에서 다음 차례의 경로 이동을 제한하는 문제가 발생하는 것입니다.

 

DFS에서 이 문제를 해결하기 위해서는 앞서 탐색을 마친 경로에서 방문했었던 방문 처리 기록들을 모두 초기화해주어야 합니다. 하지만 문제에서 주어진 체스판 한 줄의 최대 길이는 300으로 최대 90,000개의 좌표가 존재할 수 있습니다. 매 경로마다 이를 초기화해주는데 따르는 시간 비용은 어마어마할 것입니다. 따라서 하나의 경로(깊이)를 우선 탐색하는 DFS 방식은 이 문제에 적합하지 않습니다.

 

 

참고자료

• https://www.acmicpc.net/problem/7562