미로 탐색

구해야 하는 것

  • (n, m)의 위치로 이동할 때 지나야 하는 최소 칸 수

주어진 자료

  • 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸
  • 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동 가능
  • 칸을 셀 때에는 시작 위치와 도착 위치도 포함

조건

  • 2 ≤ N, M ≤ 100

계획

  1. 이동 칸 수 = 1로 시작한다.
  2. 시작점을 큐에 넣고 방문 처리를 한다. visited에 현재 이동 칸 수를 넣어준다.
  3. 큐에서 노드를 꺼낼 때 이동 칸 수를 증가시킨다.
  4. 꺼낸 노드의 인접노드 중 방문하지 않은 노드를 전부 큐에 삽입한다.
  5. visited에 현재 이동 칸 수를 넣어준다.
  6. 현재 노드가 (n, m)이면 이동 칸 수를 반환한다.

실행

class Node {
    int x;
    int y;

    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
}

public class Main {
    public int solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n, m 입력
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 미로 입력
        int[][] map = new int[n][m];
        for(int i = 0; i < n; i++) {
            String s = br.readLine();
            for(int j = 0; j < m; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }

        int[][] visited = new int[n][m]; // 방문 여부
        int move = 1; // 이동 칸 수

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

        Queue<Node> queue = new LinkedList<>();
        Node node = new Node();
        node.setX(0);
        node.setY(0);
        queue.add(node);
        visited[0][0] = move;

        while(!queue.isEmpty()) {
            // 큐에서 노드 꺼낼 때 이동 칸 수 증가
            Node front = queue.poll();
            int x = front.getX();
            int y = front.getY();
            move = visited[x][y] + 1;

            // 현재 노드가 n, m이면 이동 칸 수 반환
            if((x == n - 1) && (y == m - 1)) {
                return visited[x][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 &&
                        visited[nx][ny] == 0 &&
                        map[nx][ny] == 1
                ) {
                    Node nextNode = new Node();
                    nextNode.setX(nx);
                    nextNode.setY(ny);
                    queue.add(nextNode);
                    visited[nx][ny] = move;
                }
            }
        }

        return 0;
    }

    public static void main(String[] args) throws IOException {
        System.out.println(new Main().solution());
    }
}