백준 2178 미로탐색

https://www.acmicpc.net/problem/2178

문제해결

bfs 가장 기본적인 문제로 처음 풀 때는 이해하기 힘들었는데 하다보니까 이해되기 시작했다!

처음 위치에서 마지막 위치로 이동할 때 지나야 하는 최소 칸 수를 구하기 위해 bfs로 구현하였다.
인접한 곳을 탐색하면서 갈 수 있으면서 이전에 방문하지 않은 곳에 대하여 이전 좌표에서 +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;

public class Main {
    static int n;
    static int m;
    static int[][] map;
    static boolean[][] check;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Queue<Node> queue;

    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];
        check = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = input.charAt(j) - '0';
            }
        }
        bfs(0, 0);
        System.out.println(map[n-1][m-1]);
    }

    public static void bfs(int x, int y) {
        queue = new LinkedList<>();
        queue.add(new Node(x, y));
        check[x][y] = true;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if (map[nx][ny] == 1 && !check[nx][ny]) {
                        queue.add(new Node(nx, ny));
                        check[nx][ny] = true;
                        map[nx][ny] = map[node.x][node.y] + 1;
                    }
                }
            }
        }
    }
}

class Node {
    int x;
    int y;

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