자바(Java) 알고리즘 문제풀이 미로탈출 [이코테 / BFS]

 

 

 

---

 

 

문제 설명

동빈이는 N * M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 괴물이 있어 이를 피해 탈출해야 한다.

동빈이의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 반씩 이동할 수 있다.

이때 괴물이 있는 부분은 0으로, 괴몰이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다.

이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 떄는 시작과 마지막 칸을 모두 포함해 계산한다.

 

 

입력 조건

첫 번째 줄에 두 정수 N,M (4<=N,M<=200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다.

각각의 수들은 공백 없이 붙어서 입력으로 제시되고, 시작 칸과 마지막 칸은 항상 1이다.

 

 

출력 조건

첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

 

 

풀이 코드

미로를 탈출하는데 최소한의 거리를 묻는 전형적인 BFS 문제이다. 

시작 지점은 항상 1이기 때문에 거리를 나타내는 2차원 배열인 dis[0][0] = 1 로 미리 초기화해준다.

사용하면 출발점 기준으로 통로를 사방으로 계산하면서 dis 배열을 채워넣고, dis[n - 1][m - 1] 를 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point2 {
    int x;
    int y;

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

public class 미로탈출 {

    static int n;
    static int m;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] map;
    static int[][] dis;
    static boolean[][] checked;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        dis = new int[n][m];
        checked = new boolean[n][m];

        // 1. map 채워넣기.
        for (int i = 0; i < n; i++) {
            String[] inputLine = br.readLine().split("");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(inputLine[j]);
            }
        }

        // 2. 시작 지점은 항상 1이기 때문에 미리 초기화
        dis[0][0] = 1;

        // 3. map 한 행씩 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && !checked[i][j]) {
                    bfs(i, j);
                }
            }
        }

        System.out.println(dis[n - 1][m - 1]);
    }

    private static void bfs(int x, int y) {
        Queue<Point2> q = new LinkedList<>();
        q.offer(new Point2(x, y));

        while (!q.isEmpty()) {
            Point2 tmp = q.poll();

            // 4방향 벡터 사용
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + tmp.x;
                int ny = dy[i] + tmp.y;

                if (nx >= 0 && ny >= 0 && nx < n && ny < m && map[nx][ny] == 1 && !checked[nx][ny]) {
                    checked[nx][ny] = true;
                    q.offer(new Point2(nx, ny));
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }
}