[백준] 2178. 미로 탐색(Java)

문제

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

풀이

2차원 배열 내 0,0 지점에서 N-1,M-1까지 도달하는데 걸리는 최단시간을 구하는 문제

입력 값을 바탕으로 2차원 배열을 형성하고

 

1) 큐 사이즈 순회 및 time 카운팅 방법

2) 큐에 다음 위치와 현재까지 걸린 시간을 넘겨주는 방법

 

두 가지 방법 중 하나를 선택해 해결하면 된다.

이러한 방식에 대한 설명은 아래 링크를 참고하면 된다.

 

2차원 배열 내에서 최단시간 탐색 방법 - [백준] 숨바꼭질

[백준] 1697. 숨바꼭질(Java)

코드

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

class Main {
    static int R, C;
    static int[][] arr;
    static boolean[][] v;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb;

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new int[R][C];
        v = new boolean[R][C];

        for(int i = 0 ; i < R ; i ++){
            String s = br.readLine();
            for(int j = 0 ; j < C ; j ++)
                arr[i][j] = s.charAt(j) - '0';
        }

        bfs();
    }

    private static void bfs() {
        Queue<int[]> q = new ArrayDeque<>();

        int cnt = 1;

        v[0][0] = true;
        q.offer(new int[]{0, 0});

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

            for (int i = 0 ; i < qSize ; i++) {
                int[] cur = q.poll();

                if (cur[0] == R-1 && cur[1] == C-1) {
                    System.out.println(cnt);
                    return;
                }

                for(int d = 0 ; d < 4 ; d ++){
                    int nr = cur[0] + dr[d];
                    int nc = cur[1] + dc[d];

                    if(!isValid(nr, nc) || v[nr][nc] || arr[nr][nc] == 0) continue;

                    v[nr][nc] = true;
                    q.offer(new int[]{nr, nc});

                }
            }

            cnt++;
        }
    }

    private static boolean isValid(int nr, int nc) {
        return (nr>=0 && nr<R && nc>=0 && nc<C);
    }
}