백준 14940번 : 쉬운 최단거리

1. 문제

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

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

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

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

출력

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

예제 입력 1 복사

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1 복사

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.annotation.Target;
import java.util.*;

public class Main {

    static int[][] distance;
    static boolean[][] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        arr = new boolean[N][M];
        distance = new int[N][M];
        int x = -1, y = -1;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int n = Integer.parseInt(st.nextToken());
                arr[i][j] = n == 1;
                if (n == 2) {
                    x = i;
                    y = j;
                }
            }
        }
        bfs(x,y);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int dist = distance[i][j];
                if (dist == 0 && arr[i][j] == true) {
                    dist = -1;
                }
                sb.append(dist).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    static void bfs(int x, int y) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (check(nx, ny)) {
                    distance[nx][ny] = distance[cur[0]][cur[1]] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }

    static boolean check(int x, int y) {
        if (x < 0 || x >= distance.length || y < 0 || y >= distance[0].length || distance[x][y] > 0) return false;
        else return arr[x][y];
    }
}

3. 해설

• bfs를 통해서 가까운 곳 부터 순회하며 이전 좌표의 최단 거리값에 1을 더하는 방식으로 해당 좌표의 최단거리를 초기화한다

4. 개선된 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static int[] distance;
    static boolean[] arr;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        arr = new boolean[N * M];
        distance = new int[N * M];
        int startX = -1, startY = -1;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int n = Integer.parseInt(st.nextToken());
                if (n == 1) {
                    arr[i * M + j] = true;
                } else if (n == 2) {
                    startX = i;
                    startY = j;
                }
            }
        }
        bfs(startX, startY, N, M);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int pos = i * M + j;
                int dist = distance[pos];
                if (dist == 0 && arr[pos]) {
                    dist = -1;
                }
                sb.append(dist).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    static void bfs(int x, int y, int N, int M) {
        int[] queue = new int[N * M];
        int head = 0, tail = 0;
        int startPos = x * M + y;
        queue[tail++] = startPos;
        distance[startPos] = 0;

        while (head < tail) {
            int pos = queue[head++];
            int curX = pos / M;
            int curY = pos % M;

            for (int i = 0; i < 4; i++) {
                int nx = curX + dx[i];
                int ny = curY + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    int nPos = nx * M + ny;
                    if (arr[nPos] && distance[nPos] == 0) {
                        distance[nPos] = distance[pos] + 1;
                        queue[tail++] = nPos;
                    }
                }
            }
        }
    }
}

1. 이중배열 → 단일 배열
   
   • N * M 범위가 int 범위를 넘지 않기 때문에 배열 하나로 x, y 좌표 모두를 담을 수 있다.
2. 큐의 배열화
   • 마찬가지로 N * M 의 범위가 int범위 내 이기 때문에 모든 좌표를 다 방문하는 경우를 배열에 담더라도 문제가 없다
   • 배열을 큐 처럼 이용하는 방식
     1. poll : 인덱스가 head인 값을 추출하고 head에 1을 더한다
     2. add: 인덱스가 tail인 값에 초기화 한 후 tail에 1을 더한다.
     3. isEmpty() : head가 tail보다 커진 경우 즉, 더이상 tail에 추가된것이 없을때