[Java] 14940 쉬운 최단거리

문제

문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 
0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력
각 지점에서 목표지점까지의 거리를 출력한다.
원래 갈 수 없는 땅인 위치는 0을 출력하고,
원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

문제 풀이

BFS를 통한 문제이다. 처음 map의 값을 입력 받을 때 값이 2인(목표지점인) 위치를 기록해 두었다가 해당 위치를 시작으로 상하좌우를 탐색하며 진행한다.

자바 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class N14940 {
    private static int[][] map;
    private static int[][] distance;
    private static boolean[][] checked;
    private static int n,m;
    private static Pos goal;

    private static final int[] dr = {-1, 1, 0, 0};
    private static final int[] dc = {0, 0, -1, 1};
    public static class Pos{
        int x,y;

        Pos(int x, int y){
            this.x = x;
            this.y = y;
        }

        public int getX(){
            return this.x;
        }

        public int getY(){
            return this.y;
        }
    }

    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());
        map = new int[n][m];
        distance = new int[n][m];

	// 답안을 -1로 초기화한다.
        for (int[] line : distance)
            Arrays.fill(line, -1);

        checked = new boolean[n][m];

//map을 한 줄씩 입력받는다.
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < m; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                // 입력받은 숫자가 0일 경우 distance에 0으로 초기화
                if(map[i][j] == 0)
                    distance[i][j] = 0;
                // 입력받은 숫자가 2일 경우 distance에 0으로 초기화하고 해당 위치를 기록
                if(map[i][j] == 2){
                    goal = new Pos(i, j);
                    distance[i][j] = 0;
                }
            }
        }

        bfs(goal.getX(), goal.getY());

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static void bfs(int x, int y) {
        Queue<Pos> queue = new LinkedList<>();
        queue.add(new Pos(x, y));
        checked[x][y] = true; // 시작점 방문

        while (!queue.isEmpty()) {
            Pos current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dr[i];
                int ny = current.y + dc[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (map[nx][ny] == 0) continue; // 방문 불가능한 곳 일 경우 패스
                if (checked[nx][ny]) continue; // 이미 방문한 곳 일 경우 패스

                queue.add(new Pos(nx, ny));
                distance[nx][ny] = distance[current.x][current.y] + 1; // 거리는 현재 거리에서 +1 한 만큼 기록
                checked[nx][ny] = true;
            }
        }
    }
}