최대 25*25사이즈 부지가 n*n 2차원 배열로주어집니다.
0은 빈공간, 1은 벽입니다.
(0,0)에서 (n-1,n-1)까지 도로를 건설하는 데 드는 최소비용을 구하세요.
이 때, 칸과 칸을 잇는 직선도로를 건설할 땐 100원이 들고 코너가 생길 때마다 500원이 과금됩니다.(의역 있음)
다익스트라로 (0,0)에서 (n-1,n-1)까지의 최단경로를 구하려 했다. 그런데 코너 개념이 생기면서 이전 엣지의 방향이 자식노드의 비용을 결정한다.
그래서 pq에 들어가는 원소들에도 "이 자식을 추천한 부모노드가 어떤 방향의 도로를 갖고 있었는지", 즉 이전도로의 방향을 저장하였다.
또한 각 장소마다 진입로에 따른 가격을 세분화 해서 dist 테이블을 만들어줬다.
int dist[25][25][4];
지금은 비싸서 선택하지 않았던 도로가 나중엔 다른 노드에서 가장 싸질 수 있어요.
같은 장소라 하더라도 이 장소를 진입하는 도로에 따라 가격이 다를 수 있다. 그럼 어떤 장소를 가는 데 4개 방향의 진입로 경로 중 가장 가격이 싼 걸 고르면 된다고 착각에 빠질 수 있다.
그런데 4개의 진입로 중 하나만 선택했을 때, 당신이 선택하지 않았던 진입로의 경로가 다른 노드를 가는 데엔 더 싸게 먹힐 수가 있다.
커서가 있는 곳이 현재 보고 있는 노드이고 노랑색 노드로의 비용을 계산한다고 할 때이다.
커서 노드까지 오는 데에 1번 경로가 1300원이고 2번경로는 1400원이다.
노랑 노드로 갈 때 1번 경로는 꺾기 때문에 100+500원이 붙고
노랑 노드로 갈 때 2번 경로는 꺾지 않아도 되기 때문에 100원만 붙는다.
한 노드까지의 비용을 하나의 값으로 획일화해버리면 이렇게 금액이 역전되는 것을 놓치게 된다.
이 점 때문에
int dist[25][25][4];
로 노드 당 4개 버전의 경로를 만들어주었다.
이 점 때문에 그냥
int dist[25][25];
를 통해 노드 당 1개 버전의 가격만 저장한 알고리즘을 수정했었다.
만약 바로다음 노드에서 역전될 수 있는지의 여부(현재 가장 싼 경로에 600원을 더한 값보다 작으냐)를 해당 노드의 가격을 입찰하는 데에 사용을 했다. 근데 이렇게 하면 3중첩 직선경로로 인해 얻을 수 있는 이익 같은 거는 고려를 못 해줘서 테케 1개가 틀리더라.
#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
struct candi{
int i,j;
int d;
int o;//orientation
candi(int ii, int jj,int dd,int oo){
i=ii;j=jj;d=dd;o = oo;
}
};
struct comp{
bool operator() (candi &a, candi &b){
return a.d>b.d;
}
};
int n;
int INF = 0x7fffffff;//처음에 500*25*25했는데 틀림
int dist[25][25][4];
int di[] = {1,-1,0,0};
int dj[] = {0,0,1,-1};
int orientation[] = {1,2,3,4};
vector<vector<int>> tab;
bool check(int i, int j,int o,int d){
return i>=0&&i<n&&j>=0&&j<n&&tab[i][j]==0&&d<dist[i][j][o];
}
int solution(vector<vector<int>> board) {
int answer = 0;
tab = board;
n = board.size();
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] = INF;
}
}
priority_queue<candi, vector<candi>,comp> q;
q.push(candi(0,0,0,0));
while(!q.empty()){
candi cur = q.top();
q.pop();
if(dist[cur.i][cur.j][cur.o]<cur.d){
//같더라도 orientation다르면 다시 돌아야됨
continue;
}
dist[cur.i][cur.j][cur.o] = cur.d;
for(int k = 0;k<4;k++){
int cd =100;
if(cur.i==0&&cur.j==0){
//이전방향상관없이 100원임
}
else{
cd+=cur.d;
if(cur.o != orientation[k]){
cd+=500;
}
}
candi child = candi(cur.i+di[k],cur.j+dj[k],cd, orientation[k]);
if(check(child.i,child.j,child.o,child.d)){
q.push(child);
}
}
}
answer = INF;
for(int k = 0;k<4;k++){
answer= min(answer, dist[n-1][n-1][k]);
}
return answer;
}