[백준] 미로 탐색 JAVA

반응형

728x90

[백준] 미로탐색 - SILVER I 2178번

---

접근

• bfs

---

풀이

미로의 길을 따라 목적지까지 가는 최단 경로를 구하는 문제이다. 미로는 1과 0으로 이루어져 있고 1에 해당하는 칸만 이동이 가능하며 목적지인 (n, m)까지의 최소 칸 수를 구해야 한다.

 

최소, 최단이라는 단어가 나오면 써야 하는 알고리즘이 있다. 너비 우선 탐색의 bfs로 레벨별로 탐색을 진행하여 bfs를 사용하면 목적지를 만나는 순간이 해당 지점과의 최단 거리이다. 가끔 이런 유형의 탐색 문제에서 bfs와 dfs 중 어떤 것을 사용해야 할지 헷갈리는데 문제에 최단, 최소 등이 있다면 거의 bfs문제라고 보면 되고 어느 지점에 도달이 가능한지, 모든 경로를 탐색과 같은 내용이 있다면 거의 dfs를 사용하는 문제이다. 이번 문제도 사실 DFS와 BFS 문제의 코드를 가져왔긴 했지만 거의 절반 이상을 수정한 것 같아서 링크는 걸지 않겠다.

    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Step{
        private final int x;
        private final int y;
        private final int count;

        public Step(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }

우선 탐색을 수행하는데 2차원 배열의 좌표로 진행을 하기 때문에 상하좌우 움직임을 위한 배열이 추가되었다. 그리고 현재 좌표와 이동 칸 수를 저장할 count 변수를 가진 객체를 큐에 넣어 사용할 예정이다.

	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        int[][] maze = new int[n][m];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(line[j]);
            }
        }

        System.out.println(bfs(maze, n, m));

좌표를 입력 받아 미로를 2차원 배열로 만들어주고 bfs 함수를 호출하는 코드이다.

private static int bfs(int[][] maze, int n, int m) {
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(0,0,1));

        boolean[][] isVisited = new boolean[n][m];
        isVisited[0][0] = true;

bfs를 구현한 함수이다. 문제에서는 (1,1)에서 출발하여 (n, m)까지의 최소 거리이지만 실제 사용되는 좌표는 (0,0)~(n-1, m-1) 이 된다. 그래서 큐에 초기값으로 0, 0과 출발 및 도착 지점도 칸 수에 포함해야 하기 때문에 count 값을 1로 준다.

	while (!queue.isEmpty()) {
            Step step = queue.poll();
            int x = step.x;
            int y = step.y;
            int count = step.count;

            if (x == n - 1 && y == m - 1) {
                return count;
            }

탐색에 해당하는 부분으로 큐에서 꺼낸 좌표가 목적지 좌표와 같다면 탐색을 종료하고 목적지까지의 칸 수를 반환한다. bfs의 경우 레벨별로, 옆으로 퍼져 나가며 탐색을 하기 때문에 목적지에 도착하는 그 거리가 최소거리가 되지만 dfs로 구현할 경우 0,0 주변부터 깊숙하게 진행하여 목적지로 가기 때문에 목적지에 도착한다 하더라도 최단 경로라는 보장이 없다. 그래서 dfs의 경우 모든 경로 탐색이 끝날 때까지 구해진 값들을 계속 비교해 주며 최솟값을 찾아야 한다.

	   for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 0) {
                    continue;
                }

                if(isVisited[nx][ny])
                    continue;

                queue.offer(new Step(nx, ny, count + 1));
                isVisited[nx][ny] = true;
            }
         }
         return -1;

 상하좌우로 칸을 이동하는 부분으로 다음으로 움직일 곳이 미로 범위를 벗어나는지와 해당칸의 값이 0으로 움직일 수 없는 칸인가을 검사한다. 그리고 다음칸이 방문 했던 곳인지를 검사하고 방문하지 않았다면 큐에 다음 좌표를 추가하고 방문 체크를 한다. 만약 목적지 까지 도달할 수 없다면 -1을 반환하게 된다. dfs의 경우에는 과정은 동일하지만 for문이 끝난 뒤 다시 기존 x, y 좌표의 방문을 false로 변경해주어야 한다. dfs 알고리즘은 해당 경로 탐색이 끝나면 이전 위치로 다시 돌아와 다음 경로를 탐색해야 하는데 돌아올 경로의 방문값이 true로 되어 있다면 다음 경로 탐색을 진행할 수 없기에 스택에 추가한 뒤 꼭 다시 방문하지 않은 상태로 돌려놔야 한다.

위: bfs, 아래: dfs

 

성능 비교를 위해 dfs로도 구현한 뒤 돌려봤으나 시간 초과로 통과조차 되지 않았다. 물론 내 코드에서 더 최적화하고 할 것이 남아있겠지만 최단 거리를 구하는 데는 그만큼 bfs를 사용해야 한다는 소리다.

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    private static final int[] dx = {0, 0, 1, -1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Step{
        private final int x;
        private final int y;
        private final int count;

        public Step(int x, int y, int count) {
            this.x = x;
            this.y = y;
            this.count = count;
        }
    }

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

        String[] NM = br.readLine().split(" ");
        int n = Integer.parseInt(NM[0]);
        int m = Integer.parseInt(NM[1]);

        int[][] maze = new int[n][m];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(line[j]);
            }
        }

        System.out.println(bfs(maze, n, m));

        br.close();
    }

    private static int bfs(int[][] maze, int n, int m) {
        Queue<Step> queue = new LinkedList<>();
        queue.offer(new Step(0,0,1));

        boolean[][] isVisited = new boolean[n][m];
        isVisited[0][0] = true;

        while (!queue.isEmpty()) {
            Step step = queue.poll();
            int x = step.x;
            int y = step.y;
            int count = step.count;

            if (x == n - 1 && y == m - 1) {
                return count;
            }

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= m || maze[nx][ny] == 0) {
                    continue;
                }

                if(isVisited[nx][ny])
                    continue;

                queue.offer(new Step(nx, ny, count + 1));
                isVisited[nx][ny] = true;
            }
        }
        return -1;
    }
}