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

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

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

1. 유형

DP, BFS

 

2. 로직

 

테스트 케이스가 약간 빈약한것 같다. 반례가 존재하는 코드가 통과가 된다.

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

dp에 그때마다 최소값을 저장하면 위와 같은 반례가 존재함.

이것을 해결하기 위해 dp[4방향][y][x]처럼 3차원을 사용해서 이전의 방향에 따라 코스트를 전부 저장해준다.

일반적인 bfs에 위와같이 3차원 배열을 사용하면 되는 문제였다.

 

 

로직

1. bfs를 돌리면서 다음칸의 비용보다 더 작으면 이동가능, 큐에 삽입

 

 

3. 코드

import java.util.*;
class Solution {
    static int N, M, answer;
    static int dir[][] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
    static int[][][] dp;
    public int solution(int[][] board) {
        answer = Integer.MAX_VALUE;
        N = board.length;
        M=board[0].length;
        dp = new int[4][N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++)
                for(int k=0; k<4; k++)
                    dp[k][i][j] = Integer.MAX_VALUE;
        }
        bfs(0,0, board);
        return answer;
    }
    static void bfs(int r, int c, int[][] board){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{r,c, -1, 0});
        dp[0][r][c] = 0;
        while(!q.isEmpty()){
            int cur[] = q.poll();
            if(cur[0]==N-1 && cur[1]==M-1){
                answer = Math.min(answer, cur[3]);
                continue;
            }
            for(int i=0; i<4; i++){
                int nr=cur[0]+dir[i][0];
                int nc=cur[1]+dir[i][1];
                if(nr<0||nr>=N||nc<0||nc>=M||board[nr][nc]==1) continue;
                int nextcell=cur[3]+calc(cur[2], i);
                if( nextcell <= dp[i][nr][nc]){
                    dp[i][nr][nc] = nextcell;
                    q.add(new int[]{nr, nc, i, nextcell});
                }
            }
        }
    }
    
    static int calc(int d, int nextd){
        if(d== -1)
        	return 100;
    	if(d==nextd){
            return 100;
        }else{
            return 600;
        }
    }
}
/*
로직
직선도로 100, 커브 500
디피 문제
1) queue [좌표, 이전방향, 코스트]
2) 내가 더 작아야지 이동가능
*/

 

비슷한 문제로 백준-말이되고픈 원숭이(1600)이 있다.

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

https://moons-memo.tistory.com/188

백준 - 1600 말이되고픈 원숭이 (Java)