2020 Kakao internship 67259 - 경주로 건설(다익스트라, 0-1 bfs) c++

- N by N의 벽이 중간중간 존재하는 경주로에서 상하좌우로 도로가 놓이는데 N, N까지 도달할 수 있는 최소비용의 도로를 놓아야된다. 

- 출발지와 도착지가 정해져있는 구간의 최소비용을 구하는 로직으로는 다익스트라 알고리즘이 있어서 바로 그 알고리즘으로 접근하였다. 
(개인적으로 하는 알고리즘 스터디에서 어떤 분이 0-1 bfs 라는 로직을 사용한 것을 보았는데 이를 이용하면 O(V + E)복잡도로 풀 수 있다. 다익스트라는 우선순위큐를 이용할 시에 O((V+E)logV)이다. 

- 주의할 점으로는 코너가 발생할시 건설비용이 100이 아니라 600이 되는데, 그 것을 모든 칸의 건설비용을 계산 할 때 이전에 있었던 칸의 방향정보를 가져와서 지금 방향과 비교해서 수평이면 100, 수직이면 600으로 계산하는 방식을 사용하였다. 

#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int d[25][25][4]; // r,c, dir 상하좌우

struct Pos {
    int r, c, dir, w;
    bool operator<(const Pos& other) const {
        return w > other.w; // minheap
    }
};

int solution(vector<vector<int>> board) {
    int len = board.size(); // 정사각형
    
    memset(d, INF, sizeof(d));
    for(int i = 0; i < 4; ++i) {
        d[0][0][i] = 0; // 시작점
    }
    
    priority_queue<Pos> pq;
    pq.push({0, 0, -1, 0}); // r,c,dir,weight, 0,0 시작은 코너 예외
    
    while(!pq.empty()) {
        const auto [r, c, dir, w] = pq.top();
        pq.pop();
        
        for(int i = 0; i < 4; ++i) { // 0,1,2,3
            int nr = r + dr[i];
            int nc = c + dc[i];
            int nDir = i;
            int nw = w + 100; // 여기서 +100, 코너이면 +500
            
            if(0 > nr || 0 > nc || len <= nr || len <= nc) continue;
            if(board[nr][nc] == 1) continue;
            
            if(dir == 0 || dir == 1) { // 상하였을 때 좌우면 코너, 좌우일때 상하면 코너
                if(nDir == 2 || nDir == 3) nw += 500;
            }
            if(dir == 2 || dir == 3) {
                if(nDir == 0 || nDir == 1) nw += 500;
            }
            
            if(nw < d[nr][nc][nDir]) {
                d[nr][nc][nDir] = nw; // 최소값
                pq.push({nr, nc, nDir, nw});
            }
        }
    }
    
    int ans = *min_element(d[len-1][len-1], d[len-1][len-1] + 4);
    return ans;
}

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

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