백준 2178 - 미로탐색

링크

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

문제 풀이

기본적인 BFS 문제다. 조건에 맞춰 값을 읽어온 후 탐색을 진행하면 원하는 값을 얻을 수 있다.

전체 소스

import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static int height, width;
    public static int[] dx = { 0, 0, 1, -1 };
    public static int[] dy = { 1, -1, 0, 0 };
    public static int[][] map;

    public static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        boolean check[][] = new boolean[height + 1][width + 1];
        q.offer(new int[] { 0, 0 });
        check[0][0] = true;

        int count = 0;

        while (!q.isEmpty()) {
            int qSize = q.size();
            count++;

            while (qSize-- > 0) {
                int[] point = q.remove();
                int cntY = point[0];
                int cntX = point[1];

                if (cntY == height - 1 && cntX == width - 1) {
                    return count;
                }

                for (int i = 0; i < 4; i++) {
                    int nY = cntY + dy[i];
                    int nX = cntX + dx[i];

                    if (0 <= nY && nY < height && 0 <= nX && nX < width) {
                        if (check[nY][nX] == false && map[nY][nX] == 1) {
                            check[nY][nX] = true;
                            q.offer(new int[] { nY, nX });
                        }
                    }
                }
            }
        }

        return count;
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputValues = br.readLine().split(" ");

        height = Integer.parseInt(inputValues[0]);
        width = Integer.parseInt(inputValues[1]);

        map = new int[height + 1][width + 1];

        for (int h = 0; h < height; h++) {
            String inputValue = br.readLine();

            for (int w = 0; w < width; w++) {
                // System.out.println(inputValue.charAt(w));
                map[h][w] = inputValue.charAt(w) - '0';
            }
        }

        int count = bfs();
        System.out.println(count);

        br.close();
    }
}