[백준]14940- 쉬운 최단거리 문제 풀이(Java,자바)

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

들어가며

전형적인 bfs 문제이다.

 

코드

package solved.ac.class3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class 백준14940_쉬운최단거리 {
    private final static int[] DX = {1, 0, -1, 0};
    private final static int[] DY = {0, -1, 0, 1};
    private static int[][] map, result;
    private static boolean[][] isVisited;
    private static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = reader.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);

        map = new int[n][m];
        result = new int[n][m];
        isVisited = new boolean[n][m];

        int startX = -1, startY = -1;
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(reader.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2) {
                    startX = i;
                    startY = j;
                }
            }
        }

        bfs(startX, startY);
        printResult();
    }

    private static void bfs(int x, int y) {
        Queue<Position> queue = new ArrayDeque<>();
        queue.add(new Position(x, y));
        isVisited[x][y] = true;

        while (!queue.isEmpty()) {
            Position poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + DX[i];
                int nextY = poll.y + DY[i];

                if (isValidMove(nextX, nextY)) {
                    queue.add(new Position(nextX, nextY));
                    result[nextX][nextY] = result[poll.x][poll.y] + 1;
                    isVisited[nextX][nextY] = true;
                }
            }
        }
    }

    private static boolean isValidMove(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m && map[x][y] == 1 && !isVisited[x][y];
    }

    private static void printResult() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && !isVisited[i][j]) {
                    builder.append("-1 ");
                } else {
                    builder.append(result[i][j]).append(" ");
                }
            }
            builder.append("\n");
        }
        System.out.print(builder);
    }

    static class Position {
        public int x, y;

        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

풀이

"모든 지점에 대해서 목표지점까지의 거리를 구하여라"

위 문장을 반대로 말하면 목표지점에서 출발해서 모든 지점까지의 거리를 기록하면 그만이다.

그러므로 넓게 탐색을 진행하는 bfs를 사용한다면 빠르게 계산할 수 있다.

int startX = -1, startY = -1;
for (int i = 0; i < n; i++) {
    map[i] = Arrays.stream(reader.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

    for (int j = 0; j < m; j++) {
        if (map[i][j] == 2) {
            startX = i;
            startY = j;
        }
    }
}

시작점은 목표지점이다.

그렇기에 처음 이 좌표를 기억해둔다.

bfs(startX, startY);

목표지점에서 bfs를 돌리면 된다.

static class Position {
    public int x, y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

이 문제에선 두 좌표에 대한 기록이 계속해서 필요하므로

Position이라는 클래스를 만들었다.

 

private static void bfs(int x, int y) {
    Queue<Position> queue = new ArrayDeque<>();
    queue.add(new Position(x, y));
    isVisited[x][y] = true;

    while (!queue.isEmpty()) {
        Position poll = queue.poll();
        for (int i = 0; i < 4; i++) {
            int nextX = poll.x + DX[i];
            int nextY = poll.y + DY[i];

            if (isValidMove(nextX, nextY)) {
                queue.add(new Position(nextX, nextY));
                result[nextX][nextY] = result[poll.x][poll.y] + 1;
                isVisited[nextX][nextY] = true;
            }
        }
    }
}

bfs는 Queue를 사용하여 구현하였다.

여기선 DX, DY를 나눴지만 2차원 배열로 방향을 표현해도 무방하다.