[백준] 쉬운 최단거리

📖 문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

✍ 입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

📄 출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  
  
public class Main {
  
    static int[] moveX = {-1, 1, 0, 0};  
    static int[] moveY = {0, 0, 1, -1};  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int n = Integer.parseInt(st.nextToken());       // 세로의 크기  
        int m = Integer.parseInt(st.nextToken());       // 가로의 크기  
  
        int[] start = new int[2];  
        int[][] map = new int[n][m];  
        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;  
                }  
            }  
        }  
  
        int[][] arr = new int[n][m];  
        for(int i=0; i<n; i++) {  
            Arrays.fill(arr[i], -1);        // arr '배열 도달할 수 없는 위치' -1로 초기화  
        }  
  
        bfs(start[0], start[1], arr, map);  
  
        StringBuilder sb = new StringBuilder();  
        for(int i=0; i<n; i++) {  
            for(int j=0; j<m; j++) {  
                // map 배열에서 갈 수 없는 땅이면 0, 아니면 arr 배열의 값을 append
                if(map[i][j] == 0) {  
                    sb.append(0).append(" ");  
                } else {  
                    sb.append(arr[i][j]).append(" ");  
                }  
            }  
            sb.append("\n");  
        }  
        System.out.println(sb.toString());  
    }  
  
    public static void bfs(int x, int y, int[][] arr, int[][] map) {  
        Queue<int[]> queue = new LinkedList<>();  
        boolean[][] visited = new boolean[arr.length][arr[0].length];  
  
        // 처음 목표지점 queue 값 추가, visited true, arr 값 0 입력  
        queue.offer(new int[]{ x, y });  
        visited[x][y] = true;  
        arr[x][y] = 0;  
        while(!queue.isEmpty()) {  
            int[] val = queue.poll();  
  
            for(int i=0; i<4; i++) {  
                int dx = val[0] + moveX[i];  
                int dy = val[1] + moveY[i];  
  
                if(dx < 0 || dx > arr.length-1 || dy < 0 || dy > arr[0].length-1) continue;  
                if(visited[dx][dy]) continue;  
                if(map[dx][dy] == 0) continue;  
  
                visited[dx][dy] = true;  
                queue.offer(new int[]{dx, dy});  
                arr[dx][dy] = arr[val[0]][val[1]] + 1;  
            }  
        }  
    }  
}

🧩 코드풀이

해당 문제는 BFS를 이용하여 목표지점까지의 최단거리를 구하여 문제를 풀었습니다.
1. 우선 목표 지점 확인을 위해 2로 값이 입력되는 부분의 배열 위치를 확인합니다.
2. 이후 입력을 받는 배열 map과 bfs로 거리를 구하는 arr 배열을 선언하고, arr 배열은 우선 전체 값을 도달할 수 없는 위치를 의미하는 -1로 전체 값을 초기화합니다.
3. 이후 Queue를 활용하여 BFS를 구현하고 map배열의 0 값을 가지는 위치들은 0으로, 다른 위치들은 arr배열의 값으로 StringBuilder에 추가하여 출력해줍니다.