경주로 건설

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

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

<java>

import java.util.*;
class Solution {
    
//    static int[][] board;
    static int min = Integer.MAX_VALUE;
    static int n;
    static boolean[][] check;
    static int [][][]pmap; //방향에 대해서도 따져주어서 가격을 저장해주어야 한다. 
    static int dx[] ={-1,1,0,0}; //위,아래,왼,오
    static int dy[] ={0,0,-1,1};
    class Node{
        int x;
        int y;
        int price;
        int dir;
        Node(int x, int y, int price, int dir){
            this.x = x;
            this.y = y;
            this.price = price;
            this.dir = dir;
        }
    }
    
    boolean cango (int x, int y){
        return x>=0 && x<n && y>=0 && y<n;
    }
    
    void dfs(int[][] board, Node node){
        
        if(node.price>=min){return;}
        if(node.x==n-1 && node.y== n-1 ){
            min = Math.min(min,node.price);
            return;
        }
        
        int x = node.x;
        int y = node.y;
        int price = node.price;
        int dir = node.dir;
        
        for(int i =0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            int ndir = i;
            int nprice =0;
            
            if(dir!=-1){
            if((ndir/2)!=(dir/2)){
                nprice = price+600;
            }
            else{
                nprice = price+100;
            }
            }
            else{
                nprice = price+100;
            }
            
            if(cango(nx,ny)&&!check[nx][ny]&&(board[nx][ny]==0)){
            if((pmap[nx][ny][ndir]!=0) && (pmap[nx][ny][ndir]<=nprice)){ 
                    continue;
            }
                pmap[nx][ny][ndir]=nprice;  // 더 싼 경우에 저장을 해준다. 메모이제이션
                
                check[nx][ny]=true;
                dfs(board,new Node(nx,ny,nprice,ndir));
                check[nx][ny]=false;
                
            }
        }
        
        
    }
    
    
    public int solution(int[][] board) {
        int answer = 0;
        
        n = board.length;
        check = new boolean[n][n];
        pmap = new int[n][n][4];
        check[0][0]=true;
  
        dfs(board, new Node(0,0,0,-1));

        answer = min;
        return answer;
    }
}

<c++>

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

int dx[] = {-1,1,0,0}; //왼,오,위,아래 0,1,2,3
int dy[] = {0,0,-1,1}; 
//0,1,2,3
vector<vector<bool>>check(30,vector<bool>(30,false));

int cost[26][26][4]; //cost 저장할떄 방향도 따져주어야 한다. 왜냐하면 들어온 방향에 따라서 


void dfs(vector<vector<int>>&board, int i, int j, int way ,int total){
    
    int n= board.size();
    
    if(cost[i][j][way]!=0 && cost[i][j][way]<total){return;}
    else{cost[i][j][way]=total;}  //cost에 저장을 해주자 cost 값보다 클경우에 검사를 안해서 빨라진다. 
    
    if(i==n-1 && j==n-1){
      
        return;
    }
    
  
    for(int t=0; t<4; t++){
        
        int nx = i+ dx[t];
        int ny = j+ dy[t];
        if(nx>=0 && nx<n && ny>=0 && ny<n ){
                //cout<<"i:"<<i<<"j"<<j; 
            if(board[nx][ny]==0 && check[nx][ny]==false){
            if(t==0 || t==1){
             //   cout<<"i:"<<i<<"j"<<j;  
                if(way==2 || way==3){
                    check[nx][ny] = true;
                    dfs(board,nx,ny,t,total+600);   
                    check[nx][ny] = false;
                }
                else{
                    check[nx][ny] = true;
                    dfs(board,nx,ny,t,total+100);
                    check[nx][ny] = false;
 
                }
                
            }
            else if (t==2||t==3){
                //cout<<"i:"<<i<<"j"<<j;  
                 if(way==0 || way==1){
                    check[nx][ny] = true;
                    dfs(board,nx,ny,t,total+600);
                     check[nx][ny] = false;
                }
                else{
                    check[nx][ny] = true;
                    dfs(board,nx,ny,t,total+100);
                     check[nx][ny] = false;
                }
                }
            }
        }
    }
 
    return;
    
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    int n = board.size();
    memset(cost,0,sizeof(cost));
    dfs(board,0,0,-1,0);
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cost[i][j];
        }
    }
    int minnum = 9999999999;
    for(int i=0; i<4; i++){
        if(cost[n-1][n-1][i]!=0){
       minnum = min(minnum ,cost[n-1][n-1][i]);
        }
    }
    answer = minnum;
    
    
    return answer;
}

- DFS로 풀었다 

- cost라는 배열로 해당 지점까지의 최소 통행료를 저장하는 메모이제이션을 써야한다. 그리고 메모이제이션할때 쓰는 배열은 방향도 고려한 3차원 배열이어야한다.