[백준] 14940: 쉬운 최단거리 - JAVA

https://www.acmicpc.net/problem/14940

풀이

목표지점이 주어지고 지도의 모든 지점에서 목표지점까지의 거리를 구하는 문제이다.

목표지점부터 시작해서 bfs탐색을 통해 거리를 갱신해주었다.

원래 갈 수 없는 땅은 0으로 출력하고 도달할 수 없는 위치는 -1로 해야하는데

bfs탐색 중 처음만난 0은 0으로 처리 되지만 만나지 않는 0들은 -1로 되는 문제가 있어서

입력받을 때 0을 배열에 입력해 놓고 시작했다.


메모리: 51672KB

시간: 668ms

언어: Java 11

코드

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

public class Main {
    static class Node {
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int n, m;
    static int[][] map, result;
    static Queue<Node> queue = new LinkedList<>();

    static int[][] vector = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

    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];
        result = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(result[i], -1);
        }
        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) {
                    queue.add(new Node(i, j));
                    result[i][j] = 0;
                }
                if (map[i][j] == 0) {
                    result[i][j] = 0;
                }
            }
        }

        bfs();
    }

    private static void bfs() {
        Node start = queue.peek();
        result[start.r][start.c] = 0;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int dist = result[node.r][node.c];

            for (int i = 0; i < 4; i++) {
                int nr = node.r + vector[i][0];
                int nc = node.c + vector[i][1];

                if (nr < 0 || nc < 0 || nr >= n || nc >= m || result[nr][nc] != -1) {
                    continue;
                }

                if (map[nr][nc] == 1) {
                    result[nr][nc] = dist + 1;
                    queue.add(new Node(nr, nc));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

}