[백준, 자바] 14940번 쉬운 최단거리, bfs

1. 문제

2. 코드

(targetX, targetY)는 탐색을 시작할 지점이다. 목표 지점(숫자 = 2)을 탐색 시작 지점으로 결정하고 상하좌우로 탐색하면 된다.

• arr 배열 : 입력으로 받은 값들
• answer 배열 : 출력할 값들
  • for문에서 answer 값을 초기화한다.
  • if(num == 1) : 탐색하여 도착할 수 있는 지점
  • 초기 값을 -1로 하는 이유는 출력 예시에 설명되어 있듯이, "원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 를 만족해야 하기 때문이다.
  • bfs를 돌면서 answer에는 현재 위치(x, y)에 도착하기까지 이동한 횟수가 담긴다.
• answer[cy][cx] = answer[y][x] + 1
  • answer[cy][cx] : 현재 위치
  • answer[y][x] : 현재 위치를 도착하기 이전의 위치
  • (x, y) 위치에서 1칸 이동하여 (cx, cy) 위치에 도착한 것이므로, answer[y][x]에 담긴 이동 횟수 + 1을 하여 answer[cy][cx]에 저장하면 된다.

public class Main {

    static int N, M;
    static int[][] arr;
    static int[][] answer;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] inputArr = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();
        N = inputArr[0];
        M = inputArr[1];

        arr = new int[N][M];
        answer = new int[N][M];
        int targetX = -1;
        int targetY = -1;
        for (int i = 0; i < N; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                int num = Integer.parseInt(str[j]);
                arr[i][j] = num;
                if (num == 2) {
                    targetX = j;
                    targetY = i;
                } else if (num == 1) {
                    answer[i][j] = -1;
                }
            }
        }

        bfs(targetX, targetY);

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

        System.out.println(sb);
    }

    static void bfs(int startX, int startY) {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{startX, startY});
        arr[startY][startX] = 0;

        while (!que.isEmpty()) {
            int[] pos = que.poll();
            int x = pos[0];
            int y = pos[1];
            for (int d = 0; d < 4; d++) {
                int cx = x + dx[d];
                int cy = y + dy[d];
                if (isNotOutOfRange(cx, cy) && answer[cy][cx] == -1) {
                    answer[cy][cx] = answer[y][x] + 1;
                    que.offer(new int[]{cx, cy});
                }
            }
        }
    }

    static boolean isNotOutOfRange(int x, int y) {
        return x >= 0 && y >= 0 && x < M && y < N;
    }
}