백준 14940번 쉬운 최단거리: BFS 거리와 미방문 칸 구분하기

목표 지점에서 한 번 탐색합니다

모든 이동의 거리가 1이라서 큐를 사용하는 BFS로 거리를 구했습니다. 지도에서 값이 2인 목표 지점의 좌표를 start에 저장하고 그 지점을 탐색의 시작점으로 삼습니다.

시작점의 거리를 0으로 바꾸고 방문 표시를 한 뒤 큐에 넣어 둡니다. 큐에서 꺼낸 칸은 상하좌우를 확인합니다. 범위 안에 있고 아직 방문하지 않은 땅이면 큐에 넣습니다. 새 칸의 거리는 현재 칸의 거리보다 1 큽니다.

별도의 거리 배열 대신 map에 거리를 덮어썼습니다. 원래 땅을 나타내는 값 1과 거리 1이 겹칠 수 있기 때문에 방문 여부는 visited로 따로 관리합니다.

출력할 때 세 경우를 구분합니다

방문한 칸은 계산한 거리를 출력합니다. 방문하지 않았지만 원래 땅이었던 칸은 목표 지점에서 도달할 수 없으니 -1입니다. 원래 갈 수 없는 칸은 0으로 남깁니다.

Java

if(visited[i][j]) bw.write(map[i][j] + " ");
else if (!visited[i][j] && map[i][j] == 1) bw.write("-1" + " ");
else bw.write("0" + " ");

당시 제출 코드

Java

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

class Main {

    static int[][] map;
    static boolean[][] visited;
    static int N, M;
    static Queue<Pos> q = new LinkedList<>();

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

    static int[] opsX = {1, -1, 0, 0};
    static int[] opsY = {0, 0, 1, -1};
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine(), " ");

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

        map = new int[N][M];
        visited = new boolean[N][M];

        int[] start = new int[2];

        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) {
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        bfs(start[0], start[1]);
        printMap();
    }

    static void bfs(int i, int j) {
        q.offer(new Pos(i, j));
        visited[i][j] = true;
        map[i][j] = 0;
        while (!q.isEmpty()) {
            Pos node = q.poll();

            for (int k = 0; k < 4; k++) {
                int nX = node.x - opsX[k];
                int nY = node.y - opsY[k];

                if (checkRange(nX, nY)) {
                    if (map[nX][nY] == 1 && !visited[nX][nY]) {
                        q.offer(new Pos(nX, nY));
                        visited[nX][nY] = true;
                        map[nX][nY] = map[node.x][node.y] + 1;
                    }
                }
            }
        }
    }

    static boolean checkRange(int x, int y) {
        return -1 < x && x < N && -1 < y && y < M;
    }

    static void printMap() throws IOException {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(visited[i][j]) bw.write(map[i][j] + " ");
                else if (!visited[i][j] && map[i][j] == 1) bw.write("-1" + " ");
                else bw.write("0" + " ");
            }
            bw.write("\n");
        }
        bw.flush();
    }
}