[프로그래머스/Java] '게임 맵 최단거리'(BFS/DFS 문제) 풀이

프로그래머스의 알고리즘 고득점 Kit 중 BFS/DFS 문제 중 하나인 '게임 맵 최단거리'를 자바로 풀어봤다.

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

프로그래머스

 

우선 처음에는 이 문제를 DFS로 접근했다. 끝까지 들어가서 상대팀 진영(우측 맨아래)에서부터 하나씩 더해나가며 캐릭터의 위치에 최솟값을 넣는 것으로 했다. 하지만 이 방법으로 할 경우, 효율성이 BFS에 비해 심각하게 저하된다. 한 위치에 여러번 방문해야 하는 경우가 너무 많아진다. 

 그래서 결국 BFS로 바꾸어 접근했다. (통상적으로 모든 위치 방문을 위해서는 DFS를, 효율적 방문을 위해서는 BFS를 사용한다고 하기도 한다.) 좌표 (0, 0)에서 0이 아닌 값을 가진 위치로 하나씩 더해가며 가는 것이다. 

BFS를 사용할 경우 훨씬 효율적이어지는 이유는 한 번 방문한 위치가 최소가 맞는지 다시 확인할 필요가 없기 때문이다. 한 번의 방문만으로 해당 위치의 그 값이 최소임을 확신할 수 있다. 아래 그림의 경우를 보면, 파란색 화살표가 최단거리이다. 이때 갈림길이 총 두 번 발생하는데, 빨간색 화살표의 경우 반대방향으로 돌아서 이미 왔던 길을 다시 거쳐오기 때문에 당연히 위치를 이동해가며 하나씩 더해가는 과정에서 제외된다. 노란색의 경우는 왔던 경로를 다시 거치지는 않으나, 파란색 화살표보다 늦게 파란색 화살표와 다시 겹치는 지점인 (3, 4)에 도착하게 된다. 즉, 먼저 도착한 파란 화살표값이 당연히 최소일 수밖에 없고, 늦게 도착한 노란 화살표의 값은 고려하지 않아도 된다.

 

 이를 반영해서 아래와 같이 코드를 작성했다. queue에 있는 좌표의 4개의 이웃들을 모두 확인하는데, 이웃들의 좌표가 유효할 경우(이미 방문하지 않았고, 벽이 아닌 경우)만 일련의 계산과정을 수행하고 queue에 넣는다. 일련의 계산과정이라 함은 그냥 현재 좌표에 1을 더해주는 것이다. 현재 탐색 중인 좌표의 이웃이고, 아직 방문하지 않았다면, 현재 좌표보다 한 칸 더 가서 도달해야 하는 지점이기 때문이다.

 이 과정을 queue가 비어질 때까지 해주면 bfs로 방문이 가능하다. 다만 끝 지점까지 도달하지 못한 경우는 끝 지점의 값이 1로 남게 되니까 이를 확인해줘야 한다. (답이 1인 경우는 존재하지 않으니 안전하다. 제한사항에 1x1 배열은 주어지지 않는다는 언급이 있다.)

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        Queue<List<Integer>> que = new LinkedList<>();
        que.offer(Arrays.asList(0, 0));
        int[][] iteration = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        int x_limit = maps.length, y_limit = maps[0].length;
        
        while (!que.isEmpty()) {
            int x = que.peek().get(0);
            int y = que.poll().get(1);
            for (int[] iter : iteration) {
                int nei_x = x + iter[0];
                int nei_y = y + iter[1];
                if (nei_x < 0 || nei_x >= x_limit 
                    || nei_y < 0 || nei_y >= y_limit) continue;
                if (maps[nei_x][nei_y] == 1) {
                    maps[nei_x][nei_y] = maps[x][y] + 1;
                    que.offer(Arrays.asList(nei_x, nei_y));
                } 
            }
        }
        
        if (maps[x_limit-1][y_limit-1] == 1) return -1;
        else return maps[x_limit-1][y_limit-1];
    }
}