[BOJ] 2178. 미로탐색

 

문제 소개

 

 

 

 

BFS 풀이

 

직관적으로 보았을 때, 현재 셀을 기준으로 상하좌우로 이동하며 가능한 경로를 탐색하기 때문에 DFS나 BFS로 해결가능한 문제이다. 방문 조건 중 하나로 1인 칸으로만 이동이 가능하므로 1인 칸을 그래프에서의 하나의 노드로 볼 수 있기 때문이다. 다만 DFS로 풀었을 경우, 재귀적인 특성으로 인해 depth를 다루기가 까다롭다. 때문에 depth 대로 쭉 내려오는 것이 가능한 BFS를 사용하는 것이 더 간단한 풀이가 될 것으로 보인다. BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 바로 다음 깊이로 내려가는 식으로 동작하기 때문이다.

 

DFS와 BFS의 탐색 방식 차이

 

 

 

 

첫번째 출력 예시를 통해 예상되는 실행 결과를 확인해보았다. 시작점으로부터 출발하여 방문 가능한 셀들을 한 칸 씩 이동할때마다 1씩 증가시키고, 마지막 끝 점에 도달하면 최소 이동 칸 수를 반환한다.

 

 

 

 

주어진 테스트케이스를 만족하여 아래의 코드로 제출하였으나 시간초과 에러가 발생했다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] arr;
    static boolean[][] visited;
    public static void bfs(int row, int col) {
        int n = arr.length;;
        int m = arr[0].length;

        System.out.println(Arrays.toString(arr[0]));

        // 시작점 방문표시
        visited[row][col] = true;

        // 상하좌우
        int [][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        // Queue 선언
        Queue<int []> queue = new ArrayDeque<>();
        // 시작 지점 (x, y) 큐에 삽입
        queue.offer(new int[] {row, col});

        // 큐 빌때까지 실행
        while (!queue.isEmpty()) {
            int[] current = queue.poll();

            // row
            int x = current[0];
            // col
            int y = current[1];

            // 상하좌우 이동
            for (int[] dir: dirs) {
                // 상하좌우로 이동한 row, col의 좌표
                int dx = x + dir[0];
                int dy = y + dir[1];

                // 방문 조건
                // 인덱스가 배열을 넘어가면 안됨
                if (dx >= 0 && dx < n && dy >= 0 && dy < m) {
                    // 방문 가능 조건: 칸의 숫자가 0이 아니어야 하고 아직 방문하지 않은 상태
                    if (arr[dx][dy] != 0 && !visited[dx][dy]) {

                        visited[x][y] = true;
                        // depth 값을 갱신해줌
                        arr[dx][dy] = arr[current[0]][current[1]] + 1;
                        // 새로운 x,y를 만들어 큐에 삽입
                        queue.add(new int[] {dx, dy});
                    }
                }
            }
        }
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new int [n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j=0; j<m; j++) {
                arr[i][j] = Integer.parseInt(line.substring(j, j+1));
            }
        }

        bfs(0, 0);
        // 인덱스가 0부터 시작하니 마지막 칸의 좌표값에 -1을 해줘야함.
        System.out.println(arr[n-1][m-1]);
    }
}

 

 

 

메모리 초과 문제 해결

 

 

위의 시간초과 문제를 해결하기 위해서 bfs 함수에 리턴값을 반환하도록 하고, 큐에 현재 셀까지의 이동 횟수를 추가적으로 삽입하도록 하였다. 그리고 큐에 담긴 x, y 좌표의 값이 미로의 마지막 종점 좌표와 같다면 큐에서 받아온 최소 이동 횟수를 출력할 수 있도록 수정하였다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] arr;
    static boolean[][] visited;
    public static int bfs(int row, int col) {
        int n = arr.length;
        int m = arr[0].length;

        // 시작점 방문표시
        visited[row][col] = true;

        // 상하좌우
        int [][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        // Queue 선언
        Queue<int []> queue = new ArrayDeque<>();
        // 시작 지점 (x, y) 큐에 삽입
        queue.offer(new int[] {row, col, arr[row][col]});

        // 큐 빌때까지 실행
        while (!queue.isEmpty()) {
            int[] current = queue.poll();

            // row
            int x = current[0];
            // col
            int y = current[1];
            int count = current[2];

            if (x == n-1 && y == m-1) {
                // 최단 경로 반환
                return count;
            }

            // 상하좌우 이동
            for (int[] dir: dirs) {
                // 상하좌우로 이동한 row, col의 좌표
                int dx = x + dir[0];
                int dy = y + dir[1];

                // 방문 조건
                // 인덱스가 배열을 넘어가면 안됨
                if (dx >= 0 && dx < n && dy >= 0 && dy < m) {
                    // 방문 가능 조건: 칸의 숫자가 0이 아니어야 하고 아직 방문하지 않은 상태
                    if (arr[dx][dy] != 0 && !visited[dx][dy]) {
                        visited[dx][dy] = true;
                        // depth 값을 갱신해줌
                        arr[dx][dy] = arr[current[0]][current[1]] + 1;
                        count = arr[dx][dy];

                        // 새로운 x,y를 만들어 큐에 삽입
                        queue.add(new int[] {dx, dy, count});

                    }
                }
            }
        }
        // 도착하지 못한 경우
        return  0;
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new int [n][m];
        visited = new boolean[n][m];

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j=0; j<m; j++) {
                arr[i][j] = Integer.parseInt(line.substring(j, j+1));
            }
        }
        System.out.println(bfs(0, 0));
    }
}

 

 

 

 

 

위의 두 코드는 큰 차이가 없어 보이지만 첫 번째 코드는 최소 이동 횟수를 저장하기 위해 "arr" 배열을 사용하고 있다. arr[n-1][m-1]을 출력하여 최소 이동 횟수 결과를 내보내지만, 배열의 모든 좌표에 최소 이동 횟수를 저장하는 방식으로 작동하므로 입력 데이터 크기에 따라 메모리 사용량이 증가할 수 있다. 반면에 두 번째 코드에서는 결과를 내보내는데에 "arr" 배열을 사용하는 대신 최소 이동 횟수를 bfs 함수 내에서 직접적으로 반환하는 방식이므로 메모리 사용량이 상대적으로 적을 수 있다.