[백준/JAVA] 14940번 쉬운 최단거리 - BFS(너비 우선 탐색)

풀이

BFS 알고리즘

최단거리 문제이므로 Queue를 사용하여 BFS를 구현하였다.

시작점은 한 개

start[2]를 통해 시작점 x, y좌표를 저장한다.
BFS 시작할 때 출력 형태를 맞추기 위해 시작점을 0으로 지정하고, 미리 visited를 true로 설정해서 진행한다.

출력하기 직전에 판단

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" + " ");

조건이 3개가 존재한다.
방문했을 경우 그대로 출력한다.
방문하지 않았는데 갈 수 있었던 길이면 -1로
그 외에는 원래 못가는 길이였으므로 0으로 출력한다.

코드

제출 코드

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