[자바] 백준 2178번 미로 탐색

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

 

지나가는 최소 칸 수를 구해야하기 때문에 dfs와 bfs 중 bfs로 풀어야 한다고 한다. dfs로 풀어보진 않았지만 dfs로 풀면 시간 초과가 난다는 소식이 ... 푸는 방법은 크게 어렵지 않고 동일하게 상하좌우 방향 지정해서 인접한 곳을 방문하는 방식으로 풀면 된다. (0, 0)에서 시작하면 되고 지나가는 길마다 직전에 지나왔던 길의 값에 1을 더해주면 가장 오른쪽 아래 즉, 마지막으로 방문해야하는 곳에 도달했을 때 몇 개의 칸을 지나왔는지 알 수 있다.

 

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

public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visited;
    static int[][] graph;
    static int n;
    static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new int[n][m];
        visited = new boolean[n][m];

        for(int i = 0; i < n; i++){
            String str = br.readLine();
            for(int j = 0; j < m; j++){
                graph[i][j] = str.charAt(j) - '0';
            }
        }
        visited[0][0] = true;
        bfs(0, 0);
        bw.write(String.valueOf(graph[n-1][m-1]));
        bw.flush();
        bw.close();
    }

    static void bfs(int x, int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});

        while(!queue.isEmpty()){
            int[] now = queue.poll();
            int now_x = now[0];
            int now_y = now[1];
            for(int i = 0; i < 4; i++){
                int next_x = now_x + dx[i];
                int next_y = now_y + dy[i];
                if(next_x < n && next_y < m && next_x >= 0 && next_y >= 0) {
                    if(graph[next_x][next_y] == 1 && !visited[next_x][next_y]){
                        queue.add(new int[]{next_x, next_y});
                        graph[next_x][next_y] = graph[now_x][now_y] + 1;
                        visited[next_x][next_y] = true;
                    }
                }
            }
        }
    }
}