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

klean·2020년 12월 18일
0

문제설명

최대 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개 버전의 경로를 만들어주었다.

삽질2

이 점 때문에 그냥

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;
}

0개의 댓글