[이것이 코딩 테스트다] 미로 탈출

시간제한

1초

 

문제

동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 

미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.
동빈이의 위치는 (1, 1)이고 미로의 출구는(N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다.
이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.
미로는 반드시 탈출할 수 있는 형태로 제시된다. 

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

 

입력

첫째 줄에 두 장수 N, M (4 < N, M < 200)이 주어집니다.
다음 N개의 줄에는 각각 M개의 장수(0 혹은 1)로 미로의 정보가 주어진다.
각각의 수들은 공백 없이 붙어서 입력으로 제시된다.
또한 시작 칸과 마지막 칸은 항상 1이다.

 

입력 예시

5 6
101010
111111
000001
111111
111111

 

출력

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

 

출력 예시

10

 

---

문제 풀이 과정

미로 정보 입력받기

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

maze = new int[N][M];
visited = new boolean[N][M];

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

N과 M은 공백으로 구분되어 BufferedReader와 StringTokenizer를 통해 입력받고

얼음 틀의 정보는 공백 없이 구분해야 하므로 split을 통해 입력받았다.

 

좌표를 저장할 Point 클래스 구현

 

class Point {
    int x;
    int y;

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

 

bfs함수 구현하기

 

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하므로 BFS를 통해 해결하면 쉽다.

BFS에 대해 간단하게 살펴보고 싶다면 참고하길 바란다.

[알고리즘] BFS (Java)

 

처음 동빈이가 위치해 있는 (0, 0) 좌표, 즉 처음 좌표를 큐에 넣고 방문처리 한다.

Queue<Point> queue = new LinkedList<>();

queue.offer(new Point(0, 0));
visited[0][0] = true;

 

큐가 노드가 있는 동안 해당 과정을 반복한다.

먼저 큐의 최상단 노드를 꺼내고 해당 노드의 상하좌우를 탐색하며 다음 3가지 경우에 해당하지 않는 경우 큐에 삽입하고 방문처리를 한다.

 

1. 미로의 크기를 벗어나는 경우

2. 괴물이 있는 경우(1인 경우)

3. 방문한 경우

 

즉, 미로의 크기를 벗어나지 않고 괴물이 없고 방문하지 않은 경우 이동한다.

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

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

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
            continue;
        }

        if (maze[nx][ny] == 0 || visited[nx][ny]) {
            continue;
        }

        queue.offer(new Point(nx, ny));
        visited[nx][ny] = true;
    }
}

 

동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구해야 하므로 상하좌우로 이동하는 경우 전의 칸에서 1씩 더해준다.

즉 처음 칸은 1이므로 그다음 상하좌우로 이동할 칸은 2, 이렇게 1씩 더해가며 이동한 칸의 개수를 센다.

maze[nx][ny] = maze[x][y] + 1;

 

위에서 말했든 BFS는 시작 지점부터 가까운 노드부터 차례대로 탐색하므로 진행하다 출구를 발견하게 되면 그것이 최소 이동 칸의 개수가 된다. 따라서 나아갈 수 있는 칸의 좌표와 출구의 좌표가 일치한다면 해당 칸에서 1을 더하여 count에 저장한 후 해당 함수를 종료한다.

if (nx == N - 1 && ny == M - 1) {
    count = maze[x][y] + 1;
    return;
}

 

최종 bfs함수

static void bfs() {
    Queue<Point> queue = new LinkedList<>();

    queue.offer(new Point(0, 0));
    visited[0][0] = true;

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

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

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                continue;
            }

            if (maze[nx][ny] == 0 || visited[nx][ny]) {
                continue;
            }

            if (nx == N - 1 && ny == M - 1) {
                count = maze[x][y] + 1;
                return;
            }

            queue.offer(new Point(nx, ny));
            visited[nx][ny] = true;
            maze[nx][ny] = maze[x][y] + 1;
        }
    }
}

 

---

구현 코드

class Point {
    int x;
    int y;

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

public class TC_5_2 {
    static int[][] maze;
    static boolean[][] visited;
    static int N, M;
    static int[] dx = {-1, 1, 0, 0};  // 상하좌우
    static int[] dy = {0, 0, -1, 1};
    static int count = 0;

    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());

        maze = new int[N][M];
        visited = new boolean[N][M];

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

        bfs();
        System.out.println(count);
    }

    static void bfs() {
        Queue<Point> queue = new LinkedList<>();

        queue.offer(new Point(0, 0));
        visited[0][0] = true;

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

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

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                    continue;
                }

                if (maze[nx][ny] == 0 || visited[nx][ny]) {
                    continue;
                }

                if (nx == N - 1 && ny == M - 1) {
                    count = maze[x][y] + 1;
                    return;
                }

                queue.offer(new Point(nx, ny));
                visited[nx][ny] = true;
                maze[nx][ny] = maze[x][y] + 1;
            }
        }
    }
}

 

Reference

이것이 취업을 위한 코딩테스트다 - 나동빈