BOJ - 미로 탐색 (2178)

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

2178번: 미로 탐색

 

• 그래프 탐색 문제이다.
• 가장 빨리 탈출하는 경로를 찾으면 되므로 BFS가 유리하다.
  • 모든 경로를 찾을 필요가 없으므로 DFS는 적절하지 않다.

 

package main.java.backjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    public static final Scanner scanner = new Scanner(System.in);
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static int[][] move = new int[][]{
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };
    
    public static void main(String[] args) throws Exception {

        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int[][] map = new int[N + 1][M + 1];
        boolean[][] visited = new boolean[N + 1][M + 1];

        for (int i = 1; i <= N; i++) {
            String next = scanner.next();
            char[] chars = next.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                map[i][j + 1] = Character.getNumericValue(chars[j]);
            }
        }

        Queue<State> queue = new LinkedList<>();
        queue.offer(new State(1, 1, 1));

        while (!queue.isEmpty()) {
            State node = queue.poll();
            if (visited[node.y][node.x] == true) continue;
            visited[node.y][node.x] = true;

            //종료
            if (node.y == N && node.x == M) {
                System.out.println(node.depth);
                break;
            }

            for (int i = 0; i < move.length; i++) {
                int nextY = node.y + move[i][0];
                int nextX = node.x + move[i][1];
                if (nextY >= map.length || nextY < 0) continue;
                if (nextX >= map[0].length || nextX < 0) continue;
                if (visited[nextY][nextX] == true) continue;
                if (map[nextY][nextX] == 0) continue;
                queue.offer(new State(nextY, nextX, node.depth + 1));
            }
        }
    }
}

class State {
    public int y;
    public int x;
    public int depth;

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