(2178) 미로 탐색 (Java)

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

38

예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

13

출처

데이터를 추가한 사람: djm03178, jh05013, poia0304, sait2000

알고리즘 분류

그래프 이론
그래프 탐색
너비 우선 탐색

Solution

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ2178 {
    public static class Pair {
        int x, y;

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

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                maze[i][j] = Integer.parseInt(str.substring(j, j+1));
            }
        }
        br.close();

        Queue<Pair> q = new LinkedList<Pair>();

        int[][] dist = new int[n][m];
        for(int i = 0; i < n; i++) {
            Arrays.fill(dist[i], -1);
        }

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

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // find Start
                // 이동할 수 없는 칸이거나, 이미 방문한 칸이면 skip
                if(maze[i][j] == 0 || dist[i][j] > -1) continue;

                // Start
                q.offer(new Pair(i, j));    // 큐에 칸을 넣는다.
                dist[i][j] = 0;             // 방문처리(+ 거리계산)

                while(!q.isEmpty()) {
                    Pair pollCell = q.poll();

                    // 인접 칸 탐색
                    for(int k = 0; k < 4; k++) {
                        int nx = pollCell.x + dx[k];
                        int ny = pollCell.y + dy[k];

                        // 해당 칸이 범위를 벗어나지 않는지 체크
                        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

                        // 방문하지 않은 칸이면서, 이동 가능한 칸이면
                        if(dist[nx][ny] == -1 && maze[nx][ny] == 1) {
                            q.offer(new Pair(nx, ny));      // 큐에 칸을 넣는다.
                            dist[nx][ny] = dist[pollCell.x][pollCell.y] + 1;    // 방문처리(바로 이전 칸보다 거리가 +1)
                        }
                    }
                }

            }
        }

        // 시작칸부터 거리가 1이므로 +1 해주어야 함
        int distance = dist[n-1][m-1] + 1;

        bw.write(String.valueOf(distance));
        bw.flush();
        bw.close();
    }
}

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static int n, m;
    public static int[][] maze;
    public static int[][] dis;
    public static class Node {
        int x, y;
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static Queue<Node> q;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {-1, 1, 0, 0};

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        maze = new int[n][m];
        q = new LinkedList<Node>();
        dis = new int[n][m];
        for(int i = 0; i < n; i++) {
            Arrays.fill(dis[i], -1);
        }

        for(int i = 0; i < n; i++) {
            String str = br.readLine();

            for(int j = 0; j < m; j++) {
                char ch = str.charAt(j);
                maze[i][j] = Character.getNumericValue(ch);
            }
        }

        bw.write(String.valueOf(findGoal()));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int findGoal() {
        q.offer(new Node(0, 0));
        dis[0][0] = 1;

        while(!q.isEmpty()) {
            Node cur = q.poll();

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

                if(isNotRange(nx, ny) || dis[nx][ny] > -1 || maze[nx][ny] == 0) continue;

                q.offer(new Node(nx, ny));
                dis[nx][ny] = dis[cur.x][cur.y] + 1;
            }
        }

        return dis[n-1][m-1];

    }

    public static boolean isNotRange(int x, int y) {
        return (x < 0 || x >= n || y < 0 || y >= m) ? true : false;
    }

}

Feedback

• 방문 표시용 배열을 boolean이 아닌 int형으로 선언하므로써 방문 표시와 거리 체크를 동시에 할 수 있다.
• Arrays.fill 사용 시 2차원 배열에서는 행 기준의 반복만 해주면 된다.