[프로그래머스 Level 3] GPS (C++)

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

프로그래머스

 

 

생각 흐름

1. bfs를 돌리면서 gps_log와 현재 queue에 들어있는 것의 차이를 비교해서 차이 나는 것, gap의 개수를 queue에 저장
2. gap이 낮은 것에 대해 top으로, gap이 같을 때 time이 많이 지난 것에 대해 top으로 하여 priority queue를 적용하면 시간을 그나마 줄일 수 있을 거라 생각하여 priority queue 도입
3. 만약 -1일 경우를 대비해 queue에 너무 많은 요소가 들어있는 것을 방지 하기 위해 도착 정점으로 부터 각 노드의 거리를 잰 다음 bfs에서 현재 노드가 가지고 있는 시간으로 정점으로 갈 수 없다면 continue 처리
4. 시간 초과 발생

참고(https://school.programmers.co.kr/questions/82128)

주어진 시간 1시간 30분이 지나 답지를 봤다. (node, gap, time)에 대해 visit 처리를 하여 queue에 들어갈 것을 걸러주는 방식이었다. 이를 보고 dist로 할 시에 (node, gap, time)이 같아도 아무튼 거리가 남아있으면 queue에 넣기 때문에 중복된 요소가 계속 들어가게 되는 문제를 알았다.

 

 

#include <vector>
#include <queue>
#include <memory.h>

using namespace std;

vector<vector<int>> v;
//node, gap, time
bool visited[201][101][101];

struct cmp{
    bool operator()(pair<int, vector<int>>&a, pair<int, vector<int>>&b) {
        if(a.first==b.first){
            return a.second.size() < b.second.size();
        }else {
            return a.first > b.first;
        }
    }
};

int bfs(int k, vector<int> gps_log){
    priority_queue<pair<int,vector<int>>, vector<pair<int,vector<int>>>, cmp> q;
    q.push({0, {gps_log[0]}});
    
    while(!q.empty()){
        int gap = q.top().first;
        vector<int> tmp = q.top().second;
        q.pop();
        
        if(tmp.size() == k){
            if(tmp[k-1] == gps_log[k-1]){
                return gap;
            }
            continue;
        }
        
        if(tmp.size()==k-1){
            bool isLast = false;
            for(int i = 0; i<v[tmp.back()].size(); i++){
                if(v[tmp.back()][i]==gps_log[k-1]){
                    tmp.push_back(gps_log[k-1]);
                    q.push({gap, tmp});
                    isLast=true;
                }
            }
            if(isLast)
                continue;
        }
        
        for(int i = 0; i<v[tmp.back()].size(); i++){
            int newGap = gps_log[tmp.size()] == v[tmp.back()][i] ? gap : gap + 1;
            
            if(visited[v[tmp.back()][i]][newGap][tmp.size()]){
                continue;
            }
            visited[v[tmp.back()][i]][newGap][tmp.size()] = true;
            tmp.push_back(v[tmp.back()][i]);
            q.push({newGap, tmp});
            tmp.pop_back();
        }
    }
    return -1;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    int answer = 0;
    
    v = vector<vector<int>>(201);
    memset(visited, false, sizeof(visited));
    
    for(int i = 0; i < edge_list.size(); i++){
        v[edge_list[i][0]].push_back(edge_list[i][1]);
        v[edge_list[i][1]].push_back(edge_list[i][0]);
    }
    
    for(int i = 1; i<=n; i++){
        v[i].push_back(i);
    }
    
    answer = bfs(k, gps_log);
    
    return answer;
}