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

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

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

import java.util.*;

class Solution {
    static int[] dr={0,1,0,-1};
    static int[] dc={1,0,-1,0};
    static boolean[][] check;
    static int N;
    static int answer=Integer.MAX_VALUE;
    public int solution(int[][] board) {
        N=board.length;
        check=new boolean[N][N];
        check[0][0]=true;
        for (int i=0; i<2; i++){
            if (board[0][1]==0)
                dfs(board, 0, 1, 1, 100); //1: 가로
            if (board[1][0]==0)
                dfs(board, 1, 0, 2, 100); //2: 세로
        }
        return answer;
    }
    public void dfs(int[][] board, int r, int c, int type, int sum){
        if (sum>answer) return;
        if (r==N-1 && c==N-1){
            answer=Math.min(answer, sum);
            return;
        }
        for (int i=0; i<4; i++){
            int nr=r+dr[i];
            int nc=c+dc[i];
            int ntype=0;
            if (nr<0 || nc<0 || nr>=N || nc>=N) continue;
            if (board[nr][nc]==0 && !check[nr][nc]){
                check[nr][nc]=true;
                if (Math.abs(c-nc)==1){     //가로
                    ntype=1;
                }
                else if (Math.abs(r-nr)==1){    //세로
                    ntype=2;
                }
                if (type!=ntype){
                    dfs(board, nr, nc, ntype, sum+600);
                }
                else{
                    dfs(board, nr, nc, ntype, sum+100);
                }
                check[nr][nc]=false;
            }
        }
    }
    
}

첫번째 시도.. DFS로 풀었고 가지치기를 했으나 결과는 25개의 케이스 중 4개의 케이스가 시간 초과가 나는 현상이 발생..

 

import java.util.*;

class Solution {
    static class Pos{
        int r, c, dir, cost;
        Pos(int r, int c, int dir, int cost){
            this.r=r;
            this.c=c;
            this.dir=dir;
            this.cost=cost;
        }
    }
    static int[] dr={0,1,0,-1};
    static int[] dc={1,0,-1,0};
    static int[][][] dist;
    static int N;
    static int answer=Integer.MAX_VALUE;
    public int solution(int[][] board) {
        N=board.length;
        dist=new int[N][N][4];
        fill();
        if (board[0][1]==0){
            dist[0][1][0]=100;
        }
        if (board[1][0]==0){
            dist[1][0][1]=100;
        }
        bfs(board);
        return answer;
    }
    public void fill(){
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                for (int k=0; k<4; k++){
                    dist[i][j][k]=Integer.MAX_VALUE;
                }
            }
        }
        for (int i=0; i<4; i++){
            dist[0][0][i]=0;
        }
    }
    public void bfs(int[][] board){
        Queue<Pos> q=new LinkedList<>();
        if (board[0][1]==0){
            q.add(new Pos(0,1,0,100));
        }
        if (board[1][0]==0){
            q.add(new Pos(1,0,1,100));
        }
        while (!q.isEmpty()){
            Pos p=q.poll();
            for (int i=0; i<4; i++){
                int nr=p.r+dr[i];
                int nc=p.c+dc[i];
                int ncost=p.cost;
                if (nr<0 || nc<0 || nr>=N || nc>=N) continue;
                if (board[nr][nc]==0){
                    if (i!=p.dir){
                        ncost+=600;
                    }
                    else{
                        ncost+=100;
                    }
                    if (dist[nr][nc][i]>ncost){
                        dist[nr][nc][i]=ncost;      //최소 도착 
                        q.add(new Pos(nr, nc, i, ncost));
                    }
                }
            }
            for (int i=0; i<4; i++){
                answer=Math.min(answer, dist[N-1][N-1][i]);
            }
        }
    }
    
    
}

다른 분의 풀이를 참고하여 푼 코드..

3차원 배열을 이용하여, 각 지점까지의 최소 비용을 저장한다.

dist[r][c][d] 는 시작점에서 (r,c) 까지 d방향으로 도착했을 때의 최소 비용이다.

BFS 탐색을 해주면서, (r,c) 위치 주변 4방향에 대해 탐색을 해준 뒤 만약 dist[nr][nc][i] 의 값이 dist[r][c][d] 값+새로운 도로 건설 비용(방향 같을 때는 100원, 다를 때는 600원) 의 값보다 크다면, dist[nr][nc][i] 값을 갱신해주고, (nr, nc, i, newcost) 를 큐에 넣어줘서 탐색 대상으로 삼는다.

BFS+다익스트라 느낌의 dp 문제였다.