문제

2178번: 미로 탐색

접근

• 1(이동할 수 있는 칸)을 따라 좌표의 끝 점까지 이동한다.
• bfs를 활용한 전형적인 거리측정 문제이다.

내 코드

import java.io.*;
import java.util.*;

public class Main {
    static int[][] grid = new int[101][101];
    static int[][] distance = new int[101][101];
    static Queue<Node> queue = new LinkedList<>();
    static int[] dx = {0, 0, -1, 1}; // 상,하,좌,우
    static int[] dy = {1, -1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            String str = br.readLine(); // String 한 줄을 입력받는다.(공백x)
            for (int j = 0; j < M; j++) {
                grid[i][j] = str.charAt(j)-'0'; // 문자->int (0 또는 1)
            }
        }
        for (int[] d : distance) {
            Arrays.fill(d, -1); // 거리 계산을 위한 초기화
        }
        queue.add(new Node(0, 0));
        distance[0][0] = 1;
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int dir = 0; dir < 4; dir++) {
                int x = now.getX() + dx[dir];
                int y = now.getY() + dy[dir];
                if (x < 0 || x >= N || y < 0 || y >= M) continue;
                if (grid[x][y] != 1 || distance[x][y] >= 0) continue;
                distance[x][y] = distance[now.getX()][now.getY()] + 1;
                queue.add(new Node(x, y));
            }
        }
        System.out.println(distance[N-1][M-1]);
    }

    static class Node {
        private final int x;
        private final int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}

• bfs를 알고 있다면, 금방 풀 수 있는 대표적인 유형이다.