[BOJ] 백준 2178 미로탐색

알고리즘 재활 훈련을 하고 있다..

그래서 풀어본 문제부터 다시 풀어보면서 풀이법도 다르게하고 하나씩 하나씩 낱낱이 파악하면서 분석하는 형태로 진행하려한다.

시간이 조금 오래걸려도 결국 이렇게 진행하는게 다시 실력을 끌어올리는 것에는 가장 빠른 시도일 것이라 생각한다.

내가 이전에 미로탐색을 푼 내용은 아래 링크에 있다.

https://coder-angrybird.tistory.com/32

[백준]BOJ_2178_미로 탐색_S1

과거에 풀었을 때는 level을, 거리를 계산하기 위해서 큐에 한번에 들어간만큼 사이즈를 측정했다.

또한 출발점이 고정되어 있다는 점을 이용해서 시작을 (0,0)으로 고정하는 함수를 생성했었다.

우리가 예전에 경로탐색 수학 문제를 풀 때에 아래와 같이 꼭짓점에 숫자를 쓰면서 구했던걸 기억하는가?

분명히 학창시절에 한번쯤 이렇게 경로탐색 경우의 수 문제를 풀었던 것을 기억할 것이다.

사실 저건 경우의 수를 구하는 것이라서 최단 거리 구하는 것과는 다르다.

하지만 저런 느낌으로 출발점에서 모든 점의 거리를 그 칸 안에 숫자로 기입했다고 생각하면 된다.

하나의 예시를 들고 그려보면 이해가 쉬울 것이다.

Maze

먼저, 위와 같이 미로가 주어졌다고 해보자.
조금 더 이해하기 쉽게 0과 1을 빈 공간과 장애물로 표시를 해보면 아래와 같다.

미로의 모습

자 그럼, 이번에는 거리를 기입할 배열 Distance를 그려보자.

Distance

이 풀이에서는 예전과 다르게 큐가 그리 중요하지 않다.

어쨌든 시작해보자.
시작점 (0,0)을 방문한다.
- visisted 배열의 (0,0)을 1로 바꾸어서 방문 처리를 해준다.
- Queue에 (0,0)의 좌표를 넣어준다.(좌표는 별도 클래스를 만들어 처리한다.)
- distance 배열의 (0,0)에 1을 넣어준다. (왜냐하면 나는 '칸' 수를 거리로 측정해야하기 때문이다.)

큐에 넣었던 것을 다시 뺀다.
그럼 이제 여기서 사방탐색을 하면서 (0,0)과 붙어있던 칸들을 다시 큐에 담는다.
이때 (0,0)과 붙어있는 칸이
   1. 과거에 방문했던 적이 없어야한다.
   2. 장애물이 아니라 방문할 수 있는 칸이어야한다.
   3. 위 1번과 2번 조건을 충족했다면 이제 큐에 넣을 칸의 distance 배열의 값은 (0,0) 위치의 distance 값에 +1 을 더한다.
       이 이유는 지금 내가 구한게 (0,0)에 붙어있는 칸을 찾은 것이니, (0,0)에서 붙어있는 칸으로 가려면 거리가 +1 이 되어야한다.
그림으로 그리면 아래와 같다.

이때 Queue에 어떤 좌표가 먼저 들어가느냐는 무관하다.
여기까지 했으면 이제 감이 조금 생기지 않는가?
이걸 반복하면 된다.

(0,1)이 큐에서 빠진다.

(0,1)과 인접한 (0,2)를 큐에 넣는다.

 

(1,0)이 큐에서 빠진다.

그렇게 반복하다보면 최종 상태는 아래와 같이 된다.

 

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ2178 {

    static int N, M; // 미로의 크기를 나타내는 변수 N, M
    static boolean[][] visited; //미로의 칸을 지나갔는지 저장하는 배열 visited
    static int[][] maze; //미로 형태를 저장하는 이차원 배열 maze
    static int[][] distance; // 최단 거리(레벨)을 기록할 배열
    static int[] dx; // 사방탐색을 위한 x축 배열
    static int[] dy; // 사방탐색을 위한 y축 배열

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

        // N개의 줄에
        N = Integer.parseInt(st.nextToken());
        // M개의 정수로 미로가 주어진다.
        M = Integer.parseInt(st.nextToken());
        // 미로가 그려질 maze 배열 선언
        maze = new int[N][M];
        // 미로의 어딜 방문했는지 저장할 방문배열 visited 배열 선언
        visited = new boolean[N][M];
        // 거리를 저장할 배열 distance
        distance = new int[N][M];
        // 사방탐색 담당 x축 선언
        dx = new int[] {0, 1, 0, -1};
        // 사방탐색 담당 y축 선언
        dy = new int[] {-1, 0, 1, 0};

        // 미로를 나타내는 숫자열을 분리해서 maze 배열에 넣는다.
        for (int i = 0; i < N; i++) {
            String numbers = br.readLine();
            for (int j = 0; j < M; j++) {
                maze[i][j] = numbers.charAt(j) - '0';
            }
        }

        // maze가 제대로 그려졌는지 출력해본다.
//        for(int i = 0; i < N; i++){
//            for(int j = 0; j < M; j++){
//                System.out.print(maze[i][j] + " ");
//            }
//            System.out.println();
//        }

        // 출발점 (0, 0)에서 BFS 시작
        BFS(0, 0);

        // 최단 거리 출력 (목적지 N-1, M-1까지의 최단 경로)
        System.out.println(distance[N-1][M-1]);
    }

    // 좌표를 저장하기 위한 Coordinate 클래스 선언
    public static class Coordinate {
        private int x, y; // private로 선언

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
        // 게터 메서드
        public int getX() {
            return x;
        }
        // 게터 메서드
        public int getY() {
            return y;
        }
    }

    // 넓이 우선 탐색을 하기 위한 BFS 함수 선언
    public static void BFS(int startX, int startY) {
        // BFS를 하기 위한 queue 선언
        Queue<Coordinate> queue = new ArrayDeque<>();
        // queue에 시작점을 넣어준다.
        queue.add(new Coordinate(startX,startY));
        // 시작 좌표를 방문처리해준다.
        visited[startX][startY] = true;
        // 구해야하는 것이 지나간 '거리'가 아니라 '칸'의 수라서 출발점부터 1로 초기화한다.
        distance[startX][startY] = 1;

        while (!queue.isEmpty()){
            // 큐에서 뽑은 좌표를 저장할 Coordinate 클래스의 변수 currentCoordinate 선언
            Coordinate currentCoordiante = queue.poll();
            int x = currentCoordiante.getX();
            int y = currentCoordiante.getY();

            // 현재 방문한 한 좌표에서 상하좌우 사방탐색
            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){
                    // 만약 새로운 좌표를 방문한 적이 없고 그 지점이 이동할 수 있는 곳이라면,
                    if(visited[nx][ny] == false && maze[nx][ny] == 1){
                        // 방문한 것으로 처리한다.
                        visited[nx][ny] = true;
                        distance[nx][ny] = distance[x][y] + 1;
                        queue.add(new Coordinate(nx, ny));
                    }
                };
            }

        }
    }
}
/**
 * 똑같은 배열을 만들어서 그 배멸의 그 자리에 거리를 표기하면 된다.
 *
 */