[프로그래머스] 경주로 건설

       문제 요약        

- 문제

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

 

 

         아이디어        

- BFS 탐색은 현재 큐에 들어있는 모든 노드를 한 번씩 처리한 뒤 다음 레벨로 넘어간다. 그래서 먼저 방문한 노드가 더 적은 거리를 가지도록 보장한다. 따라서, 어떤 좌표에 도착하면 방문 여부 만으로 해당 좌표에 다시 방문하지 않는다. 

하지만, 이 문제에서는 같은 좌표라도 비용이 더 낮은 경로로 도달한 경우 다시 방문해야 한다.

따라서, 비용 테이블을 두어 중복 탐색을 방지하며 비용이 더 낮은 경우 다시 방문한다 

 

- 그리고, 우선 순위 큐를 사용함으로써 최소 비용 경로를 더 빠르게 찾을 수도 있다. 현재 비용이 낮은 노드부터 탐색하므로, 큐에 많은 노드가 들어가 있어도 빠르게  최소 경로를 찾을 수 있다. 큐의 크기가 클수록 이 점이 중요해진다.

 

처음에는 기본적인 BFS만 생각하다가 안됨을 발견하였다

DFS로 풀면 시간 초과가 난다 

         소스코드        

 

- BFS + 비용 테이블 

import java.util.*;
class Solution {
    static int[][] way = {{-1,0},{0,-1},{0,1},{1,0}};
    static int N;
    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;
        // 단순 BFS에서는 어떤 좌표에 도착하면 방문 여부 만으로 해당 좌표에 다시 방문하지 않는다. 
        // 하지만, 이 문제에서는 같은 좌표라도 비용이 더 낮은 경로로 도달했을 경우 다시 방문해야 한다. 
        N = board.length;
        int[][][] cost = new int[N][N][4]; 
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++){
                Arrays.fill(cost[i][j], Integer.MAX_VALUE);
            }
        }
        
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(new Node(0,0,-1,0));
        while(!queue.isEmpty()){
            Node now = queue.poll();
            if(now.x == N-1 && now.y == N-1){
                answer = Math.min(answer, now.c);
                continue;
            }
            for(int w = 0; w < 4 ; w++) {
                int nx = now.x + way[w][0];
                int ny = now.y + way[w][1];
                if(!inRange(nx,ny))continue;
                if(board[nx][ny] == 1)continue;
                int nextCost = now.c + (now.w == -1 || now.w == w || now.w  == 3-w ? 100: 600);
                if(cost[nx][ny][w] > nextCost) {
                    cost[nx][ny][w] = nextCost;
                    queue.add(new Node(nx, ny, w, nextCost ));
                }
            }
        }
        return answer;
    }
    static boolean inRange(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
    static class Node {
        int x, y, w, c;
        Node(int x, int y, int w, int c){
            this.x = x;
            this.y = y;
            this.w = w;
            this.c = c;
        }
    }
}

 

- BFS + 우선순위큐

우선 순위 큐를 사용하게 되면 가장 먼저 N-1, N-1에 도착하는 값의 cost가 작음이 보장된다 

현재까지 누적 비용(cost)이 가장 낮은 노드를 우선적으로 탐색하기 때문에 가장 적은 비용 경로를 찾는 과정에서 우선순위 큐를 사용하면 탐색 순서가 최적화된다