문제 링크

미로 탐색 문제와 매우 비슷하지만 미로 탐색이 조금 더 쉬우므로 해당 문제가 풀리지 않는다면 먼저 푸는 것을 추천한다.

풀이

최단거리를 구해야하고, n*m이 최대 $10^6$이며 시간제한이 1초이므로 BFS로 충분히 풀이할 수 있다.
문제의 조건은 모든 지점으로부터 목표지점까지의 거리를 구하는 것이지만 반대로 목표지점에서 모든 지점까지의 거리를 구해도 같은 결과가 나온다.

주어진 입력 값들을 저장할 이차원 배열 map과 목표지점까지의 거리를 저장할 이차원 배열 dist를 선언한다.
입력 값들을 저장하며 목표지점을 의미하는 2가 나오면 i, j의 값을 따로 저장한다.
갈 수 없는 지점을 의미하는 0이 나오면 dist 값을 0으로, 나머지는 -1로 초기화해준다.

목표지점부터 bfs를 돌며 이동할 수 있는 곳의 dist 값을 현재 지점까지의 거리 + 1로 갱신해준다.

코드

package BOJ;

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

public class sol14940 {
    static int n, m;
    static int[][] map;
    static int[][] dist;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        dist = new int[n][m];

        int targetX = 0;
        int targetY = 0;
        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());
                if (map[i][j] == 2) {
                    targetX = i;
                    targetY = j;
                }
                if (map[i][j] == 0) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = -1;
                }
            }
        }
        bfs(targetX, targetY);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(dist[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static void bfs(int x, int y) {
        Queue<Coord> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];
        q.add(new Coord(x, y));
        dist[x][y] = 0;
        visited[x][y] = true;

        while (!q.isEmpty()) {
            Coord c = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = c.x + dx[i];
                int ny = c.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny] || map[nx][ny] == 0) {
                    continue;
                }
                dist[nx][ny] = dist[c.x][c.y] + 1;
                visited[nx][ny] = true;
                q.add(new Coord(nx, ny));
            }
        }
    }

    public static class Coord {
        int x, y;

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