14940번 : 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

문제

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

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

 

입력

지도의 크기 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.*;

public class Main {
    static int map[][];
    static int distance[][];
    static int n,m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        distance = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                distance[i][j] = -1;
            }
        }

        int startX = 0, startY = 0;
        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) {
                    startX = i;
                    startY = j;
                    distance[i][j] = 0;
                } else if(map[i][j] == 0) distance[i][j] = 0;
            }
        }

        bfs(startX, startY);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                sb.append(distance[i][j] + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    static int rx[] = {0, 0, -1, 1};
    static int ry[] = {-1, 1, 0, 0};
    static void bfs(int x, int y) {
        Deque<int[]> deque = new ArrayDeque<>();
        deque.addLast(new int[]{x, y});

        while(!deque.isEmpty()) {
            int[] now = deque.pollFirst();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + rx[i];
                int ny = now[1] + ry[i];

                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if(distance[nx][ny] != -1) continue;
                if(map[nx][ny] == 0 || map[nx][ny] == 2) continue;

                deque.addLast(new int[]{nx, ny});
                distance[nx][ny] = distance[now[0]][now[1]] + 1;
            }
        }
    }
}

 

해결방법

목표 지점을 출발 지점으로 생각하고 문제를 풀면 간단해진다.

거리를 나타내는 distance 배열을 하나 두고 BFS를 수행하면 된다.

 

주의할 점으로는 문제의 "원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다."를 못 보고 문제를 풀었다.

이를 위해 distance 배열을 처음에 -1로 초기화시켜주고 따로 0과 2 지점은 0으로 설정해 주었다.

 

그래야 아래 테스트가 통과한다.

input
3
2 0 1
0 1 1
1 1 1

output
0   0 -1
0  -1 -1
-1 -1 -1