[백준] 14940 쉬운 최단거리 - BFS

문제 링크 : https://www.acmicpc.net/problem/14940

🍊해결방법

• arr2 배열에 문제에서 주어진 arr 배열 중 2와 0을 0으로 저장하고 나머지는 -1로 저장
• 2인 좌표에서 시작해서 -1인 아직 도착하지 않은 지역으로 이동
• 이동하면서 전의 거리 d + 1을 저장
• 중복방문의 우려는 이미 -1인 곳만 방문하기 때문에 고려 X
• print로 출력하게되면 시간이 오래 걸리니 StringBuilder 활용

😀풀이

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

public class Main {

    static class Node{
        int x, y, d;

        public Node(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }

    }


    static int N;
    static int M;
    static int[][] arr;
    static int[][] arr2;
    static Queue<Node> q;
    static int[] dx = {-1, +1, 0, 0};
    static int[] dy = {0, 0, -1, +1};


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

        arr = new int[N][M];

        arr2 = new int[N][M];

        int sx = 0;
        int sy = 0;

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 2){
                    sx = i;
                    sy = j;
                    arr2[i][j] = 0;
                    continue;
                }

                if (arr[i][j] == 0){
                    arr2[i][j] = 0;
                    continue;
                }

                arr2[i][j] = -1;

            }
        }

        q = new LinkedList<>();

        bfs(sx, sy);


        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                sb.append(arr2[i][j]+" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);


    }

    static void bfs(int x, int y){

        q.add(new Node(x, y, 0));

        while(!q.isEmpty()){

            Node p = q.poll();

            for(int i=0; i<4; i++){

                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M){

                    if (arr2[nx][ny] == -1){
                        q.add(new Node(nx, ny, p.d+1));
                        arr2[nx][ny] = p.d + 1;
                    }

                }

            }

        }
    }


}