문제

풀이

이해

2차원 공간의 지도가 주어진다. 지도는 2차원 좌표로 위치를 특정할 수 있으며 각 공간은 0, 1, 2의 값을 갖는다. 값에 대한 의미는 다음과 같다.

0 : 갈 수 없는 땅
1 : 갈 수 있는 땅
2 : 목적지

모든 공간에 대하여 목적지에 도달할 수 있는 최단거리를 구해야 한다.
단, 0인 공간은 그대로 0을 출력하며 1이지만 0에 의해 가로막혀 갈 수 없는 공간은 -1로 표현한다.

접근

이웃하는 공간의 거리는 항상 1로 일정하기 때문에 최단거리는 단순히 몇 칸 떨어져 있는지 구하면 된다.

그렇다면 최단거리를 구할 때의 방법에 대해서 생각해보자.

2차원 공간을 모두 순회하면서 해당 위치에 대하여 목적지까지의 거리를 각각 구하면 될까?

그래프 상의 최단거리를 구하기 위해서는 BFS를 활용할 수 있다. 위 방법의 경우에는 NxM 상의 모든 공간을 기준으로 BFS를 수행하면 시간복잡도가 급격히 증가하는 것을 알 수 있다.

BFS 1회 수행 시 시간복잡도를 O(BFS)라고 한다면 전체 시간복잡도는 N*M*O(BFS)이다.

사실 위 방법처럼 모든 공간에 대해서 BFS를 수행할 필요는 없다. 방향을 뒤집어 목적지에서부터 BFS를 수행하고 방문하는 공간에 대한 거리를 계산하면 BFS 1회만으로 모든 거리 값을 구할 수 있기 때문이다.

구체적인 과정은 다음과 같다.

1. 지도를 나타낼 2차원 배열 생성
2. 목적지 특정
3. 목적지를 기준으로 BFS 수행
4. 0인 공간을 제외하고 모든 노드 방문
5. 출력

코드

package java_baekjoon;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class prob14940 {
    static int N;
    static int M;
    static int[][] map;
    static int[][] ans;
    static boolean[][] visited;
    static int[] r_d = { -1, 0, 1, 0 };
    static int[] c_d = { 0, -1, 0, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int start_x = -1;
        int start_y = -1;

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        ans = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(ans[i], 0);
        }
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();

                if (map[i][j] == 2) {
                    start_x = i;
                    start_y = j;
                }
            }
        }

        bfs(start_x, start_y);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    sb.append(-1 + " ");
                } else {
                    sb.append(ans[i][j] + " ");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());

        sc.close();
    }

    public static void bfs(int x, int y) {
        Queue<node> q = new LinkedList<>();
        q.add(new node(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            node now = q.poll();

            for (int i = 0; i < 4; i++) {
                int next_x = now.x + r_d[i];
                int next_y = now.y + c_d[i];

                if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y]) {
                    if (map[next_x][next_y] == 1) {
                        ans[next_x][next_y] = ans[now.x][now.y] + 1;
                        q.add(new node(next_x, next_y));
                        visited[next_x][next_y] = true;
                    }
                }
            }

        }
    }
}

class node {
    int x;
    int y;

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

결과

피드백

최초에는 메모리 초과가 발생했다. 그 이유는 다음 코드를 보자.

메모리 초과 코드

    public static void bfs(int x, int y){
    	Queue<node> q = new LinkedList<>();
        q.add(new node(x, y));

        while (!q.isEmpty()) {
            node now = q.poll();
            visited[now.x][now.y] = true;

            for (int i = 0; i < 4; i++) {
                int next_x = now.x + r_d[i];
                int next_y = now.y + c_d[i];

                if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y]) {
                    if (map[next_x][next_y] == 1) {
                        ans[next_x][next_y] = ans[now.x][now.y] + 1;
                        q.add(new node(next_x, next_y));
                    }
                }
            }

        }
    }

수정 코드

    public static void bfs(int x, int y) {
        Queue<node> q = new LinkedList<>();
        q.add(new node(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            node now = q.poll();

            for (int i = 0; i < 4; i++) {
                int next_x = now.x + r_d[i];
                int next_y = now.y + c_d[i];

                if (next_x >= 0 && next_x < N && next_y >= 0 && next_y < M && !visited[next_x][next_y]) {
                    if (map[next_x][next_y] == 1) {
                        ans[next_x][next_y] = ans[now.x][now.y] + 1;
                        q.add(new node(next_x, next_y));
                        visited[next_x][next_y] = true;
                    }
                }
            }

        }
    }

이전 코드와 수정 코드의 차이점은 노드 방문 시 방문 여부(true, false)에 대한 수정은 언제 하는가에 있다.

이전 코드에서는 큐에서 노드를 뺀 뒤 수정한 반면 수정 코드는 방문하기 전 큐에 삽입과 동시에 수정하였다.

이전 코드처럼 작성하면 큐에 들어간 노드(미래에 방문할 노드)는 큐에서 나오기(poll) 전까지는 계속 false 상태이기 때문에 다른 노드 검사시에 반복해서 큐에 삽입될 수 있다.

따라서, 미래에 방문할 노드는 큐에 삽입 시에 곧바로 true 바꿔주어 이후에 큐에 중복으로 삽입되는 것을 막아야 한다.