프로그래머스 - 1844번: 게임 맵 최단거리 [Java] [실패]

문제: https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

1. 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;
        int[][] distance = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                distance[i][j] = -1;
            }
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        distance[0][0] = 1;

        int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

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

            for (int[] direction : move) {
                int newX = x + direction[0];
                int newY = y + direction[1];

                if (newX >= 0 && newX < n && newY >= 0 && newY < m && maps[newX][newY] == 1 && distance[newX][newY] == -1) {
                    distance[newX][newY] = distance[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }

        return distance[n - 1][m - 1];
    }
}

2. 설명

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

n은 maps의 행과 m은 maps의 열의 값을 저장하며 행과 열에 맞추어 distance를 생성하여 -1을 저장합니다. distance는 maps의 각 최단 경로를 업데이트하는데 사용됩니다.

Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
distance[0][0] = 1;

(0, 0)에서 출발하기에 큐에 넣으며 distance에는 해당 위치에 1을 저장합니다. 왜냐하면 최단 경로가 (0, 0)은 1이기 떄문이빈다.

int[][] move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

move는 배열의 이동을 나타내기 위해서 사용됩니다. (우, 상, 하, 좌)

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

    for (int[] direction : move) {
        int newX = x + direction[0];
        int newY = y + direction[1];

        if (newX >= 0 && newX < n && newY >= 0 && newY < m && maps[newX][newY] == 1 && distance[newX][newY] == -1) {
            distance[newX][newY] = distance[x][y] + 1;
            queue.offer(new int[]{newX, newY});
        }
    }
}

큐가 비어질 때까지 반복하는데 큐에 저장된 것 중 가장 앞에 있는 것을 제거한 값을 cureent에 저장 후, for each문을 통해 move의 값을 받아서 각 위치가 maps 안에 존재하며 방문을 하지 않고 maps에 1 즉, 이동 가능한 곳이라면 1을 distance[x][y] + 1을 하여 최단 거리를 저장하며 큐에 추가해줍니다.

이를 반복하면서 벽을 제외한 인접한 위치의 최단 거리를 구할 수 있습니다. 따라서 목표 지점인 maps의 오른쪽 아래 끝부분까지의 최단 거리가 구해집니다.

return distance[n - 1][m - 1];

만약 최단 거리를 구하지 못했다면 distance를 처음 -1로 전부 초기화했기에 -1이 반환되며 아니라면 최단 거리가 반환됩니다.

3. 느낀점

이제 DFS에 간신히 이해하여 사용할 수 있게되어 이번 문제도 DFS로 해결하려고 했지만 시간 초과 문제를 해결할 수 없어서 찾아보니 BFS를 통해서 해결한다면 해결될 수 있었으며 BFS의 코드를 이해하며 활용할 수 있게 노력해야겠다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges