(C++) - 프로그래머스(2017 카카오 코드 본선) : 튜브의 소개팅

programmers.co.kr/learn/courses/30/lessons/1839

코딩테스트 연습 - 튜브의 소개팅

 

다익스트라 문제였습니다.

 

풀이방법

 0,0부터 시작해 s를 초과하지 않으면서 가장 짧은 경로를 찾아야 합니다. 우선순위를 tuple 자료구조를 이용해 [지나온 친구의 수, 스트레스 양, x행, y열]로 지정해줍니다. 이를 최소 heap인 우선순위 queue에 넣어줍니다. 

 

우선순위 큐가 차 있는 동안 다음을 수행 합니다.

 1. top에 있는 원소를 pop한다면 우선순위에 의해 가장 짧은 경로가 나옵니다.

 

 2. 해당 경로를 거쳐온 지점 x행 y열부터 시작해 상하좌우를 확인합니다. 상하좌우에 해당하는 행,열 좌표는 nx,ny에 저장합니다. 파티장의 크기를 넘지않는 nx,ny에 한해서 nx,ny로 갔을 때 쌓이는 스트레스 수치를 nextCost에 저장합니다. 현재까지의 스트레스 수치 + nextCost가 s이하인 지점은 갈 수 있습니다.

 

 3. 기존 nx,ny로 왔을 때 스트레스 수치보다 아까 구한 값이 더 작다면 갱신해줘야합니다. nx,ny좌표로 갔을 때 스트레스 수치는 speakTime 변수에 저장됩니다. 갱신된 후 다음 경로를 찾기 위해 pq에 자료들을 저장해줍니다. 

 

 4. 만약 m-1, n-1목적지에 도착했고 더 짧은 경로가 있다면 경로와 스트레스수치를 vector변수 answer에 갱신해줍니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using pllll = tuple<ll,ll,ll,ll>;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
int M, N, S;
ll speakTime[51][51];

vector<vector<int>> board;

vector <int> dijsktra(){
    vector <ll> answer = {INF,INF};
    speakTime[0][0] = 0;
    priority_queue <pllll,vector<pllll>,greater<pllll>> pq;
    //dist, s, x, y
    pq.push({0,0,0,0});
    while(!pq.empty()){
        auto [dist,cost,x,y] = pq.top();
        
        pq.pop();

        for(int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if(0 > nx || nx >= M || 0 > ny || ny >= N) continue;

            ll nextCost = board[nx][ny];

            if(board[nx][ny] == -1 || cost + nextCost > S) continue;

            if(cost + nextCost < speakTime[nx][ny]){
                speakTime[nx][ny] = cost + nextCost;
                pq.push({dist+1,speakTime[nx][ny],nx,ny});
                if(nx != M - 1 || ny != N - 1) continue;
                if(answer[0] < dist + 1) continue;
                answer[0] = dist+1;
                answer[1] = speakTime[nx][ny];
            }
        }
    }

    int a = answer[0];
    int b = answer[1];

    return {a,b};
}

vector<int> solution(int m, int n, int s, vector<vector<int>> time_map) {
    M = m, N = n, S = s, board = time_map;
    for(int i = 0; i <= 50; i++)
        for(int j = 0; j <= 50; j++) speakTime[i][j] = INF;
    return dijsktra();
}