[Baekjoon] 14940 쉬운 최단거리 - JAVA

문제

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

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

---

입력

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

---

📝 제출 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

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

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

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

        int targetX = -1, targetY = -1;
        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());
                distance[i][j] = -1;
                if (map[i][j] == 2) {
                    targetX = i; targetY = j;
                }
            }
        }

        BFS(targetX, targetY);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    sb.append(0).append(" ");
                } else {
                    sb.append(distance[i][j]).append(" ");
                }
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    public static void BFS(int targetX, int targetY) {
        Queue<int[]> queue = new LinkedList<>();

        queue.add(new int[]{targetX, targetY});
        visited[targetX][targetY] = true;
        distance[targetX][targetY] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && map[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    distance[nx][ny] = distance[x][y] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

 

 

이 문제는 BFS 알고리즘을 사용해 2차원 배열에서 특정 위치로부터 최단 거리를 계산하는 프로그램이다.

 

 

전역 변수 선언하기

가장 먼저 BFS 메서드를 따로 구현해야 하므로 접근이 용이하도록 static으로 전역 변수들을 선언해주었다.

입력 받은 지도를 저장할 2차원 배열 map과 각 지점의 방문 여부를 기록할 2차원 배열 visited,

목표 지점에서 각 지점까지의 거리를 저장할 2차원 배열 distance를 선언한다.

n, m은 지도의 크기 즉, 각각 지도의 행과 열을 저장할 변수이다.

dx와 dy는 x축과 y축 각 상하좌우 이동을 표현하기 위한 1차원 배열이다.

static int[][] map;
static boolean[][] visited;
static int[][] distance;
static int[] dx = {0, 0, 1, -1};  // 이동 방향: 오른쪽, 왼쪽, 아래, 위
static int[] dy = {1, -1, 0, 0};  // 이동 방향: 오른쪽, 왼쪽, 아래, 위
static int n, m;

 

 

입력받기

BufferedReader와 StringTokenizer를 통해 지도의 크기 n과 m을 입력 받아,

map, visited, distance 를 각각 n, m 크기로 초기화 해준다.

 

map은 for문을 통해 숫자를 입력받아 초기화 하면서 목표 지점인 2를 찾는다. 동시에 목표 지점의 좌표는 targetX, targetY에 저장한다. 이동할 수 없는 지점(0)과 아직 방문하지 않은 지점의 distance는 -1로 초기화 한다.

 

st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());

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

int targetX = -1, targetY = -1;
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());
        distance[i][j] = -1;
        if (map[i][j] == 2) {
            targetX = i; targetY = j;
        }
    }
}

 

 

BFS 함수

Queue를 사용해 BFS를 수행한다.

목표 지점에서 시작해 상하좌우로 인접한 칸을 탐색한다.

새로운 칸에 도달하면 현재 칸의 거리를 +1로 기록해준다.

 

(x, y)는 현재 위치이고

(nx, ny)는 다음 이동할 위치를 계산한다.

인덱스 i가 0부터 3까지 반복되면서 dx, dy 배열의 상하좌우 이동 방향으로 이동을 시도하게 된다.

 

조건문을 통해 이동 조건에 적합하면

방문 기록을 true로 설정하고,

새로운 위치까지의 거리를 현재 위치의 거리 +1 해준다.

그리고 새로운 위치 (nx, ny)를 큐에 추가하고, 큐가 비어있을 때까지 BFS 탐색을 계속 진행한다.

 

새로운 위치로 이동이 가능한 조건은 다음과 같다.

 

if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && map[nx][ny] == 1)

 

1. nx와 ny가 지도 범위 내에 있는지

2. 방문 기록이 false인지

3. 지도의 숫자가 1로 갈 수 있는 땅인지

위 세 가지 조건을 모두 만족해야 새로운 위치로 이동할 수 있다.

public static void BFS(int targetX, int targetY) {
    Queue<int[]> queue = new LinkedList<>();

    queue.add(new int[]{targetX, targetY});
    visited[targetX][targetY] = true;
    distance[targetX][targetY] = 0;

    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int x = current[0];
        int y = current[1];

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];	// 현재 x에서 이동 방향을 더해 새로운 x 좌표 계산
            int ny = y + dy[i];	// 현재 y에서 이동 방향을 더해 새로운 y 좌표 계산
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && map[nx][ny] == 1) {
                visited[nx][ny] = true;
                distance[nx][ny] = distance[x][y] + 1;
                queue.add(new int[]{nx, ny});
            }
        }
    }
}

 

 

결과 출력

결과 출력은 StringBuilder로 문자열을 조합하고, BufferedWriter로 출력하도록 했다.

갈 수 없는 땅은 그대로 0을 저장하고, 도달할 수 없는 지점은 -1(초기값)로 저장한다.

그 외의 거리들은 BFS 탐색을 통해 구한 결과값을 저장하여 최종 문자열을 출력한다.

 

 

시간 복잡도

BFS에서의 시간 복잡도는 탐색해야 할 노드의 수와 간선의 수에 따라 결정된다.

해당 문제에서 지도의 크기는 최대 1000 × 1000 으로 설정되어 있기 때문에 시간 복잡도는 O(n × m)을 만족한다.

 

제출 현황