게임 맵 최단거리

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

프로그래머스

 

Level 2

 

행렬 탐색 후 최단 경로의 거리를 구하는 문제

 

r x c 행렬의 좌측 상단인 (0, 0) 에서 출발해 (r-1, c-1) 도착하는 최단 경로를 구하고 거리를 반환해야한다.

(도착하지 못할 경우 -1 반환)

 

처음에는 DFS 를 사용해 모든 경로를 구하고 경로 중에서 최단 경로의 거리를 반환해보았는데,

정확성 케이스는 통과했지만 효율성 케이스를 통과하지 못했다.

모든 경로를 구할 필요없이 최초로 도달한 최단 경로가 정답이 되기 때문.

(실제 코딩테스트 였으면 아마 30 ~ 40분은 잡아 먹었을 것 같다)

 

그래서 BFS 로 다시 구현해보았고 최종적으로 효율성 케이스도 통과할 수 있었다. 

구현 시 주의할 점으로 경로의 거리를 다른 경로와 중복되서 사용되지 않도록 해야한다는 것

배열로 처리해도 되지만 가독성이 떨어져 그냥 커스텀 클래스를 생성해 큐의 원소로 넣었다. 

 

 

또한 방문 처리 과정에서 이미 앞서간 최단경로가 후발경로의 경로를 방해해도 상관없게 처리했고

(우리가 구하려는 건 어차피 단 하나의 가장 짧은 최단 거리일 뿐, 모든 경로를 신경쓸 필요없다)

다음 탐색 대상을 큐에 넣기전에 판별해 최대한 효율성을 높였다. 

 

 

import java.util.*;

public class Solution { //게임 맵 최단거리
    static int maxRow;
    static int maxCol;
    static int minCost;
    public int solution(int[][] maps) {
        maxRow = maps.length;
        maxCol = maps[0].length;
        minCost = Integer.MAX_VALUE;
        bfs(maps);
        return minCost == Integer.MAX_VALUE ? -1 : minCost; //최소 cost 가 바뀌지 않았으면 목적지에 도달하지 못한 것이므로 -1 반환
    }

    public void bfs(int[][] map){
        Queue<Move> queue = new LinkedList<>(); //커스텀 Class Move 생성, 좌표 + cost 값을 가짐
        queue.add(new Move(0, 0, 1)); //(0,0) 시작점 추가, 시작하는 순간 이미 방문한 것이나 다름 없으니 cost 1 증가하고 시작
        map[0][0] = 0; //시작점 방문 처리 -> 향후 탐색 시 대상에서 제외

        while(!queue.isEmpty()){
            Move move = queue.poll(); //큐 head 원소 get + remove
            if(move.r == maxRow-1 && move.c == maxCol-1){ //목적지 도착 시
                minCost = Math.min(move.cost, minCost); //최소 cost 갱신 후 종료 -> 다른 경로는 이미 최소 경로로 선정되지 못함
                return;
            }

            if(move.r + 1 < maxRow && map[move.r+1][move.c] > 0){ //남쪽 방문 확인 조건
                Move nextMove = new Move(move.r+1, move.c, move.cost+1);
                map[move.r+1][move.c] = 0; //방문처리
                queue.add(nextMove); //다음 bfs 대상으로 추가
            }
            if(move.c + 1 < maxCol && map[move.r][move.c+1] > 0){ //동쪽 방문 확인 조건
                Move nextMove = new Move(move.r, move.c+1, move.cost+1);
                map[move.r][move.c+1] = 0;
                queue.add(nextMove);
            }
            if(move.r - 1 > -1 && map[move.r-1][move.c] > 0){ //북쪽 방문 확인 조건
                Move nextMove = new Move(move.r-1, move.c, move.cost+1);
                map[move.r-1][move.c] = 0;
                queue.add(nextMove);
            }
            if(move.c -1 > -1 && map[move.r][move.c-1] > 0){ //서쪽 방문 확인 조건
                Move nextMove = new Move(move.r, move.c-1, move.cost+1);
                map[move.r][move.c-1] = 0;
                queue.add(nextMove);
            }
        }
    }

    class Move{ //커스텀 Class
        int r;
        int c;
        int cost;
        public Move(int r, int c, int cost){
            this.r = r;
            this.c = c;
            this.cost = cost;
        }
    }
}