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

문제

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

코딩테스트 연습 - 경주로 건설

경주로 건설에 필요한 최소 비용 구하기

풀이

기본적으로 BFS와 DP방식으로 문제를 접근했다. 

BFS로 영역을 확장해 나가면서 건설 비용을 저장하였다. 

방문체크는 따로 하지 않았고, 현재까지의 경로 건설 비용이 현재 위치의 저장된 건설비용보다 작을 경우 

경로 탐색을 진행하는 것으로 하였다. 

 

제출 시 마지막 테스트 케이스 제외하고 모두 정답이었다. 

아래의 오답을 뱉어내는 게 문제였다. 

 

25번 테스트 케이스 대응

테스트 데이터 

입력 : 

[[0, 0, 0, 0, 0, 0, 0, 0], 

[1, 0, 1, 1, 1, 1, 1, 0], 

[1, 0, 0, 1, 0, 0, 0, 0], 

[1, 1, 0, 0, 0, 1, 1, 1], 

[1, 1, 1, 1, 0, 0, 0, 0], 

[1, 1, 1, 1, 1, 1, 1, 0], 

[1, 1, 1, 1, 1, 1, 1, 0], 

[1, 1, 1, 1, 1, 1, 1, 0]]

정답: 4500

자동차	100	200	300	400	500	600	700
1	700	1	1	1	1	1	1300
1	800	1400	1	2200	2100	2000	1400
1	1	2000	2600	2700	1	1	1
1	1	1	1	2900	3500	3600	3700
1	1	1	1	1	1	1	4300
1	1	1	1	1	1	1	4400
1	1	1	1	1	1	1	목적지

 

오답: 4900

자동차	100	200	300	400	500	600	700
1	700	1	1	1	1	1	1300
1	800	1400	1	2200	2100	2000	1400
1	1	2000	2600	2700	1	1	1
1	1	1	1	3300	3900	4000	4100
1	1	1	1	1	1	1	4700
41	1	1	1	1	1	1	4800
1	1	1	1	1	1	1	목적지

 

정답 케이스: 2600 -> 2700 -> 3300

오답 케이스: 2200 -> 2800(이 지점에서 2700보다 더 크기 때문에 탐색이 중지됨) -> 2900

 

BEFORE

    public boolean needSearch(int x, int y, int cost) {
        if(dp[x][y] == 0) {
            // 첫 방문이면 그대로 넣는다.
            dp[x][y] = cost;
            return true;
        }
        if(dp[x][y] > cost){
            // 이미 방문한 곳이라면, 현재 경로까지의 비용이 작은 경우에만 탐색을 진행한다.
            dp[x][y] = cost;
            return true;
        }
        return false;
    }

해결 방법은 기존에 저장된 최소 건설 비용과 현재 까지의 비용을 비교해서 경로 탐색 여부를 결정할 때, 방향 정보도 이용하는 것이었다. 기존의 2차 배열인 dp를 3차 배열로 변경한 후 방향 정보도 넣어서 체크를 하니 통과되었다. 

소스코드는 아래와 같다. 

소스코드

import java.util.*;
class Solution {
    
    // x, y, dir 별 최소 건설 비용을 저장할 3차 배열
    int[][][] dp; 
    // board
    int[][] board;
    // 갈 수 있는 x, y, dir 값 후보  
    int[][] dirs = new int[][]{{-1, 0, 0}, {1, 0, 1}, {0, -1, 2}, {0, 1, 3} };
    int N;
    
    public int solution(int[][] board) {
        this.N = board.length;
        this.board = board;
        this.dp = new int[N][N][4];
        
        bfs();

        // N-1, N-1 좌표의 최소 건설 비용을 리턴한다.
        int answer = Integer.MAX_VALUE;
        for(int i= 0; i < 4; i++){
           if(dp[N-1][N-1][i] == 0) continue;
           answer = Math.min(dp[N-1][N-1][i], answer);
        }
        
        return answer;
    }

    public void bfs() {
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(0); // x (행)
        que.offer(0); // y (열)
        que.offer(-1); // 처음엔 방향이 없으므로 -1
        que.offer(0); // 비용
        board[0][0] = 1;
        
        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();
            int dir = que.poll();
            int cost = que.poll();  

            for(int[] d: dirs){
                int nx = x + d[0];
                int ny = y + d[1];
                int ndir = d[2];
                
                if(isValid(nx, ny)){ // 갈 수 있는 좌표 인지 체크
                    int ncost = isCorner(dir, ndir)? 600 : 100; // 코너 여부에 따라 비용 계산
                    if(!needSearch(nx, ny, ndir, cost + ncost)) continue; // 탐색이 필요한지 체크
                    que.offer(nx);
                    que.offer(ny);
                    que.offer(ndir);
                    que.offer(cost + ncost);
                }
            }
        }        
    }
    
    public boolean needSearch(int x, int y, int dir, int cost) {
        if(dp[x][y][dir] == 0) {
            // 첫 방문이면 그대로 넣는다.
            dp[x][y][dir] = cost;
            return true;
        }
        if(dp[x][y][dir] > cost){
            // 이미 해당 방향으로 방문한 곳이라면, 현재 경로까지의 비용이 작은 경우에만 탐색을 진행한다.
            dp[x][y][dir] = cost;
            return true;
        }
        return false;
    }
            
    public boolean isValid(int x, int y){
        if(x < 0 || y < 0 || x >= N || y >= N || board[x][y] == 1) return false;
        return true;
    }
    
    public boolean isCorner(int dir, int ndir){
        if(dir == -1) return false;
        if(dir != ndir) return true;
        return false;
    }
}