[Java] BOJ 14940 쉬운 최단거리

문제 

문제 링크 https://www.acmicpc.net/problem/14940

• 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
• 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.
• 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
• 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

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

아이디어

• 길 정보를 2차원 배열에 저장하는데 이때 값이 2가 들어온다면 도착지점의 좌표를 저장하는 변수에 저장한다.
• 그리고 저장된 도착지점의 좌표값으로 BFS를 돌리는데 BFS에서 시작점을 도착지점의 좌표값으로 해서 while문을 돌린다. (최단거리를 구해야되므로 BFS를 쓰고 목표지점이 한개이므로 역으로 생각해서 목표지점을 시작점으로 두고 모든 좌표를 방문했을 때 거리를 재면 BFS를 한번만 돌아도되기 때문이다.)
• while문에서 Queue에서 뺀 값을 기준좌표로 상하좌우 이동한 좌표값이 배열의 범위를 벗어나지 않고 방문하지 않았으며 길의 정보가 1일 때, 기준좌표값에 해당하는 거리 + 1한 값을 결과값에 저장한다.
• 그리고 방문처리를 한 후, Queue에 넣는다.
• BFS를 다 돌고 아직 방문하지 않았는데 길의 정보가 1이라면 목표지점까지 갈 수 없는 곳에 시작점이 있다는 뜻이므로 -1을 결과값에 저장해주고 결과값 배열을 출력한다.

겪은 시행착오

• X

BFS는 어느정도 감을 잡은 것 같다..!

코드

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

public class BOJ14940 {

    static int n;
    static int m;
    static int map[][];
    static int result[][];
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int end_x;
    static int end_y;
    static boolean visited[][];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 행
        n = Integer.parseInt(st.nextToken());
        // 열
        m = Integer.parseInt(st.nextToken());

        // 길을 저장할 지도
        map = new int[n][m];
        // 목표지점까지 갈 거리를 저장할 2차원 배열
        result = new int[n][m];

        // 도착지점의 x, y 좌표값
        end_x = 0;
        end_y = 0;

        // 방문처리 저장할 배열
        visited = new boolean[n][m];

        // 지도에 길 저장
        for(int i = 0; i < n; i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            for(int j = 0; j < m; j++){
                int r = Integer.parseInt(st2.nextToken());

                // 만약 입력값이 2라면 도착지점 변수에 저장
                if(r == 2){
                    end_x = i;
                    end_y = j;
                }

                map[i][j] = r;
            }
        }

        // 목표지점 좌표값으로 BFS를 돌림
        BFS(end_x, end_y);

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // 만약 아직 방문하지 않은 좌표값이 1이라면
                // 목표지점에서 시작지점까지 갈 수 없다는 뜻이므로
                // 결과값을 -1로 저장
                if(!visited[i][j] && (map[i][j] == 1)){
                    result[i][j] = -1;
                }

                sb.append(result[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }

    public static void BFS(int x, int y){
        Queue<Point> q = new LinkedList<>();

        // 시작지점을 Queue에 넣어줌
        q.offer(new Point(x, y));

        // 목표지점을 방문처리하고
        visited[x][y] = true;
        // 결과값 배열에 목표지점 값을 0으로 저장
        result[x][y] = 0;

        // Queue가 빌때까지 반복
        while(!q.isEmpty()){
            int xx = q.peek().x;
            int yy = q.peek().y;

            // Queue에서 빼줌
            q.poll();

            for(int i = 0; i < 4; i++){
                // 기준 좌표값에서 상하좌우 이동한 값
                int nx = xx + dx[i];
                int ny = yy + dy[i];

                // 만약 이동한 좌표값이 배열 범위를 넘어간다면 continue
                if(nx >= n || nx < 0 || ny >= m || ny < 0){
                    continue;
                }

                // 만약 이동한 좌표를 방문하지 않았고 배열의 값이 1이라면
                if(!visited[nx][ny] && (map[nx][ny] == 1)){
                    // 이동한 좌표값에 위치하는 결과값 배열에
                    // 기준 좌표값 위치의 값에 + 1 더한값을 저장하고
                    result[nx][ny] = result[xx][yy] + 1;
                    // 방문처리 해줌
                    visited[nx][ny] = true;
                    // 마무리로 Queue에 이동한 좌표값을 넣어줌
                    q.offer(new Point(nx, ny));
                }
            }
        }
    }
}