[프로그래머스] 게임 맵 최단거리 (Java)

프로그래머스

접근 방식

DFS(실패)

 맵에서 이동할 수 있는 모든 경우의 수를 탐색하며 최종 목적지에 도달할 때마다 최소값을 갱신하고, 경우의 수가 최대 10000개이므로 DFS로 풀면 되는 문제라고 판단했다. 다만 보통의 DFS문제들은 visited 배열을 별도로 선언하여 푸는 반면 여기서는 maps[][]가 주어지므로 방문한 경로는 벽으로 표시(0으로 표시)하는 방식으로 maps를 이용했다. 이동은 동서남북의 네 가지만 가능하므로, 한 회차마다 네 방향으로 이동가능여부를 체크하고 이동하도록 했다.

 문제는 금방 풀었으나 효율성 코드를 통과하지 못했다. 다른 사람들의 질문을 참고해보니 최단거리 구하기는 보통 전형적인 BFS 문제라고 한다. 

 

효율성 통과못한 코드(DFS, 69.9점)

class Solution {
    public int solution(int[][] maps) {
        explore(maps, 0, 0, 1);
        return min == 10000 ? -1 : min;
    }
    
    private int min = 10000;
    
    private void explore(int[][] maps, int x, int y, int count){
        
        if(x < maps.length - 1 && maps[x + 1][y] != 0){
            maps[x + 1][y] = 0;
            explore(maps, x + 1, y, count + 1);
            maps[x + 1][y] = 1;
        }
        
        if(y < maps[0].length - 1 && maps[x][y + 1] != 0){
            maps[x][y + 1] = 0;
            explore(maps, x, y + 1, count + 1);
            maps[x][y + 1] = 1;
        }
        
        if(x > 0 && maps[x - 1][y] != 0){
            maps[x - 1][y] = 0;
            explore(maps, x - 1, y, count + 1);
            maps[x - 1][y] = 1;
        }
        
        if(y > 0 && maps[x][y - 1] != 0){
            maps[x][y - 1] = 0;
            explore(maps, x, y - 1, count + 1);
            maps[x][y - 1] = 1;
        }
  
        if(x == maps.length - 1 && y == maps[0].length - 1){
            min = Math.min(min, count);
        }
    }
    
}

BFS(성공)

 최단거리 문제를 BFS를 사용하여 접근할 경우 가장 가까운 노드를 시작으로 거리가 먼 노드들을 순차적으로 탐색하게 된다. 그래서 최초로 목적지에 도착하는 경로가 바로 최단거리가 되며, 이후의 불필요한 경로 탐색을 하지 않을 수 있어 모든 경우의 수를 구하는 DFS에 비해 더 효율적이다. 물론 최악의 경우(답이 없는 경우)에는 DFS와 BFS가 모두 완전탐색을 수행하기 때문에 복잡도가 같으나(같은 자료구조로 구현했다고 가정했을 때) 시작 지점에서 가까운 거리에 답이 있는 경우에는 BFS가 효율적이다.

로직 설명

- 좌표별 정보를 저장할 Coordinate 클래스 선언(멤버변수: x좌표, y좌표, 시작점부터 해당 좌표까지의 count)

- 한 지점으로부터 동, 서, 남, 북 좌표 이동을 편리하게 표기하기 위한 moveX[], moveY[] 배열 선언

- BFS를 수행하기 위해 필요한 queue 선언, 탐색할 좌표 저장용

- queue에 (0, 0) 좌표를 count 1로 설정하여 넣어주기: new Coordinate(0, 0, 1);

- queue에 좌표가 존재하는 동안 반복:

1) 현재 좌표 poll()

2) 꺼낸 좌표가 목적지 좌표이면 해당 좌표의 count를 정답으로 설정 후 루프 종료

3) (목적지가 아니라면) 꺼낸 좌표의 동, 서, 남, 북 좌표가 maps 범위 안에 있는지 확인 및 벽(0)이 아닌지 확인 후, queue에 집어넣기. 이 때 꺼낸 좌표의 count + 1을 생성자에 넣어주기.

4) 큐에 넣은 좌표는 벽(0)으로 표시

5) 정답 반환

통과한 코드(BFS)

import java.util.*;

class Coordinate {
    private int x;
    private int y;
    private int count;
    
    Coordinate(int x, int y, int count){
        this.x = x;
        this.y = y;
        this.count = count;
    }
        
    public int getX(){
        return this.x;
    }
    
    public int getY(){
        return this.y;
    }

    public int getCount(){
        return this.count;
    }
}

class Solution {
    public int solution(int[][] maps) {
        int answer = -1;
        
        Queue<Coordinate> queue = new LinkedList<>();
        
        int[] moveX = {1, 0, -1, 0};
        int[] moveY = {0, 1, 0, -1};
        
        queue.offer(new Coordinate(0, 0, 1));

        while(queue.size() > 0){    
            Coordinate c = queue.poll();

            if(c.getX() == maps.length - 1 && c.getY() == maps[0].length - 1){
                answer = c.getCount();
                break;
            }
    
            for(int i = 0; i < moveX.length; i++){
                int tempX = c.getX() + moveX[i];
                int tempY = c.getY() + moveY[i];
                
                if(tempX >= 0 && tempY >= 0 && tempX < maps.length && tempY < maps[0].length && maps[tempX][tempY] != 0){
                    queue.offer(new Coordinate(tempX, tempY, c.getCount() + 1));
                    maps[tempX][tempY] = 0;
                }
            }
        }
        return answer;
    }
}

Note

- 습관처럼 getter를 만들어서 사용했는데, 안 만들고 작성했으면 코드가 조금 더 짧아질 수는 있었을 거 같다.