[2020 카카오 인턴십] 경주로 건설 c++ 문제 풀이 (다익스트라, 구조체)

 

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

프로그래머스

 

풀이요약: 다익스트라, 구조체

 

코드

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

int dw[4]={1,-1,0,0};
int dh[4]={0,0,1,-1};
int dist[1000][1000][2];

int INF = 98765432;

struct edge {
    int cost;
    int w;
    int h;
    bool vertical;
    //우선순위 큐에서 사용할 비교연산자를 재정의한다.
    bool operator<(edge other) const {
        return cost > other.cost; // 작은 순으로 정렬
    }
};

int getNcost(edge e,int i){
    int n_cost=0;
     if(e.w==0&&e.h==0){
                n_cost=1;
            }
            else if(i<2){ //상하
                if(e.vertical){//같은 방향 
                    n_cost=1;
                }
                else{
                    n_cost=6;
                }
                
            }
            else if(i>=2){//좌우
                if(!e.vertical){//같은 방향 
                    n_cost=1;
                }
                else{
                    n_cost=6;
                }
            }    
    return n_cost;
}

int solution(vector<vector<int>> board) {
    int answer = 0;
    memset(dist, INF, sizeof(dist));
    //직선 1, 코너 5
    priority_queue<edge> pq;
    int n=board.size();

    pq.push({0,0,0,true});
    int cnt=0;
    
    while(!pq.empty()){
        edge now=pq.top();
        int w=now.w,h=now.h;
        pq.pop();
        int n_cost=0;
                if(board[w][h]==1||dist[w][h][now.vertical]<=now.cost)continue;
         dist[w][h][now.vertical]=now.cost;
        if(w==n-1&&h==n-1){
            answer=now.cost;
            break;
        }
        for(int i=0;i<4;i++){
            int nw=w+dw[i],nh=h+dh[i];
            if(0>nw||nw>=n||0>nh||nh>=n)continue;
           
            if(board[nw][nh]==1)continue;
            
           int n_cost=getNcost(now,i); 
            
            int n_total=now.cost+n_cost;
            if(board[nw][nh]==1||dist[nw][nh][now.vertical]<=n_total)continue;
            pq.push(
                {n_total,nw,nh,(i==0||i==1)?true:false}
            );
        }
    }
   // answer=dist[n-1][n-1];
    return answer*=100;
}

다익스트라로 해결했다.

나는 코너를 아래와 같이 정의했다.

수평이동 -> 수직이동 or 수직이동 -> 수평이동 

코너를 만들어서 이동해야하는 타일로 이동시 코너생성비용, 그리고 해당 타일로 가기위한 1개의 도로를 생성해야하기에, 500+100=600의 비용이 소모된다.

 

주의

시작점에서 어떠한 지점 (x,y)로 이동 시에, 수평이동으로 해당 타일에 도착했는지, 수직이동으로 도착했는지를 구분해야한다!

만약 (x,y)에 수평이동으로 도착하면, 수직이동은 모두 코너로 돌아야한다.

반대로 (x,y)에 수직이동으로 도착하면, 수평이동은 모두 코너로 돌아야한다.

그렇기에 dist배열을 만들던 visit배열을 만들던 dist[x][y] or visit[x][y] 처럼 단순히 해당 지점으로만 구분하면 안된다.

나는 이를 구분하기 위해 dist[x][y][수직이면 0, 수평이면 1] 이런식으로 배열을 선언했다.

 

구조체

문제를 푸는데, 구조체 사용하는 것이 어색해서 관련 내용도 정리해보겠다.

 

비교연산자 재정의 하기

struct edge {
    int cost;
    int w;
    int h;
    bool vertical;
    //우선순위 큐에서 사용할 비교연산자를 재정의한다.
    bool operator<(edge other) const {
        return cost > other.cost; // 작은 순으로 정렬
    }
};

 

구조체 객체 생성

pair을 사용할 때, 중괄호를 통해 편하게 생성하는 것처럼, 구조체도 중괄호를 통해 생성할 수 있다.( 생성자를 만들어도 되지만, 귀찮다..)

구조체에서 각 멤버를 정의한 순서대로 중괄호에 넣으면된다.

 edge e={cost,w,h,vertical};
 
 pq.push({cost,w,h,vertical});