[c++] 경주로 건설 (다익스트라)

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
struct Pos{
    int y,x,cost,dir;
};
 
struct cmp{
    bool operator()(const Pos &a, const Pos &b){
        return a.cost> b.cost;
    }
};
 
int answer = 987654321;
int n;
//0:동 1:남 2:서 3:북
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
int cost[26][26][4];
int Board[26][26];
 
void bfs(){
    priority_queue<Pos,vector<Pos>,cmp> pq;
    pq.push({ 0, 0, 0, -1});
    while(!pq.empty()){
        Pos now=pq.top();
        pq.pop();
        for(int i=0;i<4;i++){
            int ny=now.y+dy[i];
            int nx=now.x+dx[i];
            int ncost=now.cost;
            int dir=now.dir;
            if(ny<0 || ny>=n || nx<0 || nx>=n)
                continue;
            if(Board[ny][nx])
                continue;
            ncost+=100;
            if(dir%2 != i%2 && dir!= -1)
                ncost+=500;
            
            if(ncost<cost[ny][nx][i]){
                cost[ny][nx][i]=ncost;
                pq.push({ny,nx,ncost,i});
            }     
        }   
    }
    answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
    
}
 
int solution(vector<vector<int>> board) {
    n=board.size();
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++ ){
            Board[i][j]=board[i][j];
        }
    }
    
     for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < 4; ++k)
                cost[i][j][k] = INF;
    for (int i = 0; i < 4; ++i)
        cost[0][0][i] = 0;
    bfs();
    
    return answer;
}

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
struct Pos{
    int y,x,cost,dir;
};
 
struct cmp{
    bool operator()(const Pos &a, const Pos &b){
        return a.cost> b.cost;
    }
};
 
int answer = 987654321;
int n;
//0:동 1:남 2:서 3:북
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
int cost[26][26][4];
int Board[26][26];
 
void dfs(int y, int x ,int curCost,int dir){
       
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        int ncost=curCost;
        if(ny<0 || ny>=n || nx<0 || nx>=n)
            continue;
        if(Board[ny][nx])
            continue;
        ncost+=100;
        if(dir%2 != i%2 && dir!= -1)
            ncost+=500;
        if(ncost<cost[ny][nx][i]){
            cost[ny][nx][i]=ncost;
            dfs(ny,nx,ncost,i);
        }     
    }     
}
 
int solution(vector<vector<int>> board) {
    n=board.size();
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++ ){
            Board[i][j]=board[i][j];
        }
    }
    
     for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < 4; ++k)
                cost[i][j][k] = INF;
    for (int i = 0; i < 4; ++i)
        cost[0][0][i] = 0;
    
    dfs(0,0,0,-1);
    answer = *min_element(cost[n - 1][n - 1], cost[n - 1][n - 1] + 4);
    return answer;
}

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

프로그래머스

다익스트라 문제 오랜만에 풀어봐서 잘못 접근했었네요.

dp문제로 처음에 시간초과가 뜬걸 주의해서 다익스트라로 해결할 수 있는 문제였습니다.