[JAVA] 백준 2178 너비 우선 탐색

 

 

 

2178번: 미로 탐색

 

문제

2차원 배열이 주어졌을 때 1이 있는 곳만 이동할 수 있다.

(0, 0)에서 (N-1, M-1)까지의 최소 경로의 이동 횟수를 구하여라 ( (0,0)에서 시작할때도 횟수 1추가 )

풀이

값을 받아준다.

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new int[N][M];
        V = new boolean[N][M];
        for(int i=0; i<N; i++){
            char[] data = br.readLine().toCharArray();
            for(int j= 0;j<M; j++){
                A[i][j] = Integer.parseInt(data[j]+"");
            }
        }

N : x좌표

M : y좌표

V : 방문 여부

A[][] : 미로 배열

char[]로 받아서 파싱해준다.

비교할 x, y좌표

    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

1,1을 기준으로 (1, 0) (1, 2) (0, 1) (2, 1), 상하좌우를 비교할 값을 미리 작성해둔다.

BFS

private static void BFS(int i, int j){
                //x, y좌표를 담아둔다.
        Queue<int[]> q = new LinkedList<>();
        V[i][j] = true;
        int depth = 1;
        q.offer(new int[] {i, j});
        while (!q.isEmpty()){
            int[] now = q.poll();
                        // 상, 하, 좌, 우를 비교
            for(int x = 0; x<4; x++){
                int a = now[0]+dx[x];
                int b = now[1]+dy[x];
                                // 배열 밖을 참조하지 않고 A[a][b]가 0이 아닐 때
                if(a >= 0 && a < N && b >= 0 && b < M && A[a][b] != 0){
                    if(!V[a][b]){
                                                // q에 담아주고 방문 여부를 체크한다. 현재 A[a][b]값에 이전(원래 좌표)까지 움직인 값 + 1을 해줘서 체크해준다.
                        q.add(new int[] {a, b});
                        V[a][b] = true;
                        A[a][b] = A[now[0]][now[1]] + 1;
                    }
                }
            }
        }
    }

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

class Main {
    static int[][] A;
    static boolean[][] V;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int N;
    static int M;

    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());

        A = new int[N][M];
        V = new boolean[N][M];
        for(int i=0; i<N; i++){
            char[] data = br.readLine().toCharArray();
            for(int j= 0;j<M; j++){
                A[i][j] = Integer.parseInt(data[j]+"");
            }
        }
        BFS(0, 0);
        System.out.println(A[N-1][M-1]);

    }

    private static void BFS(int i, int j){
        Queue<int[]> q = new LinkedList<>();
        V[i][j] = true;
        int depth = 1;
        q.offer(new int[] {i, j});
        while (!q.isEmpty()){
            int[] now = q.poll();
            for(int x = 0; x<4; x++){
                int a = now[0]+dx[x];
                int b = now[1]+dy[x];
                if(a >= 0 && a < N && b >= 0 && b < M && A[a][b] != 0){
                    if(!V[a][b]){
                        q.add(new int[] {a, b});
                        V[a][b] = true;
                        A[a][b] = A[now[0]][now[1]] + 1;
                    }
                }
            }
        }
    }

}

결과