쉬운 최단 거리

문제

14940번: 쉬운 최단거리

문제 설명

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

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

제한 사항

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

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

입출력 예

입력	출력
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1	11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1	12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0	13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1	14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

입출력 예 설명

아이디어

bfs임

제출 코드

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

public class one14940 {
    public static int rowNum;
    public static int colNum;
    public static int[][] map;
    public static int[][] answer;
    public static boolean[][] visited;
    public static int[] dRow = {0, 0, 1, -1};
    public static int[] dCol = {1, -1, 0, 0};
    
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer infoToken = new StringTokenizer(reader.readLine());

        // 지도의 사이즈 입력받기
        colNum = Integer.parseInt(infoToken.nextToken());
        rowNum = Integer.parseInt(infoToken.nextToken());

        // 지도 초기화하기
        map = new int[colNum][rowNum];
        answer = new int[colNum][rowNum];
        visited = new boolean[colNum][rowNum];

        // 시작점
        int startCol = -1;
        int startRow = -1;

        // 지도 정보 입력받기
        for (int i = 0; i < colNum; i++) {
            StringTokenizer mapInfo = new StringTokenizer(reader.readLine());
            for (int j = 0; j < rowNum; j++) {
                map[i][j] = Integer.parseInt(mapInfo.nextToken());
                if (map[i][j] == 2) {
                    startCol = i;
                    startRow = j;
                }
            }
        }

        bfs(startCol, startRow);

        // 정답 출력해 보기
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < colNum; i++) {
            for (int j = 0; j < rowNum; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    builder.append(-1 + " ");
                }
                else {
                    builder.append(answer[i][j] + " ");
                }
            }
            builder.append('\n');
        }

        System.out.println(builder);
    }

    private void bfs(int col, int row) {
        Queue<int[]> toVisit = new LinkedList<>();
        toVisit.add(new int[] {col, row});
        visited[col][row] = true;

        while(!toVisit.isEmpty()) {
            int[] now = toVisit.poll();
            int nowCol = now[0];
            int nowRow = now[1];

            for (int i = 0; i < 4; i++) {
                int nextCol = nowCol + dCol[i];
                int nextRow = nowRow + dRow[i];

                if (nextCol < 0 || nextCol >= colNum || nextRow < 0 || nextRow >= rowNum) continue;
                if (map[nextCol][nextRow] == 0) continue;
                if (visited[nextCol][nextRow]) continue;

                toVisit.add(new int[] {nextCol, nextRow});
                answer[nextCol][nextRow] = answer[nowCol][nowRow] + 1;
                visited[nextCol][nextRow] = true;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        new one14940().solution();
    }
}