[백준] 14940번 : 쉬운 최단거리 - 자바[Java]

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

14940번: 쉬운 최단거리

풀이

목표지점을 시작으로 하는 BFS를 수행하여, 각 지점까지의 최단거리를 구하면 된다.

 

주어진 지도는 map, 각 지점까지의 최단거리는 answerMap에 저장한다.

원래 갈 수 없는 위치는 0을 출력하고, 원래 갈 수 있는 땅 중에서 도달할 수 없는 위치는 -1을 출력하기 위해,
answerMap을 모두 -1로 초기화한다음, map이 0인 위치는 0으로 변경한다.

 

코드

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

public class Main {

    static int n, m;
    static int[][] map; // 지도
    static int[][] answerMap; // 최단거리를 저장하는 맵
    
    static int[] dr = {0, 0, 1, -1};
    static int[] dc = {1, -1, 0, 0};

    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];
        answerMap = new int[n][m];
        
        // answerMap을 -1로 초기화
        for (int i = 0; i < n; i++) {
            Arrays.fill(answerMap[i], -1);
        }

        int startX = 0;
        int startY = 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] == 0) {
                    answerMap[i][j] = 0; // 갈 수 없는 땅의 위치는 0으로 변경
                }
                if (map[i][j] == 2) { // 목표지점 저장
                    startX = i;
                    startY = j;
                }
            }
        }

        bfs(startX, startY);

        print();
    }

    static void bfs(int startX, int startY) {
        Queue<int[]> q = new ArrayDeque<>();
        boolean[][] visited = new boolean[n][m];

        q.add(new int[]{startX, startY});
        visited[startX][startY] = true;
        answerMap[startX][startY] = 0;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];

            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                
                // 이동할 위치가 인덱스를 벗어나지 않고, 방문하지 않았으며, 갈 수 있는 위치인 경우에만 다음을 수행
                if (nr >= 0 && nr < n && nc >= 0 && nc < m && !visited[nr][nc] && map[nr][nc] != 0) {
                    q.add(new int[]{nr, nc});
                    visited[nr][nc] = true;
                    answerMap[nr][nc] = answerMap[r][c] + 1;
                }
            }
        }

    }

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

        System.out.println(sb);
    }
}