[그래프(다익스트라)] 프로그래머스 등산코스 정하기 C++

 

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

프로그래머스

다익스트라

O(200000 * log(50000))

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer(2, 10000001);
    vector<pair<int, int>> v[50001];
    int dist[50001];
    bool top[50001];
    fill(dist, dist+50001, 10000001);
    
    for(int i=0; i<paths.size(); i++) {
        v[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        v[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 오름차순
    for(auto g : gates) pq.push({0, g});
    for(auto s : summits) top[s] = true;
    
    while(!pq.empty()) {
        auto now = pq.top();
        pq.pop();

        if (top[now.second]) continue;
        if (dist[now.second] < now.first) continue;
        
        for (auto i : v[now.second]) {
            if (dist[i.first] <= max(now.first, i.second)) continue;
            dist[i.first] = max(now.first, i.second); // 최댓값
            pq.push({dist[i.first], i.first});
        }
    }
    
    for(auto s : summits) {
        if (dist[s] < answer[1]) answer = {s, dist[s]};
        else if ((dist[s] == answer[1]) && (s < answer[0])) answer = {s, dist[s]};
    }
    
    return answer;
}

* DFS 순열 반복

13 TC부터 시간초과

O(25000 * 25000 *(50000 + 200000))

#include <string>
#include <vector>

using namespace std;

int dist;
bool visited[50001];
vector<pair<int, int>> v[50001];

void dfs(int start, int end, int path) {
    if (dist < path) return;
    if (start == end) dist = min(dist, path);
    
    for(auto vec : v[start]) {
        if (visited[vec.first]) continue;
        visited[vec.first] = true;
        dfs(vec.first, end, max(vec.second, path));
        visited[vec.first] = false;
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    vector<int> answer(2, 10000001);
    
    for(int i=0; i<paths.size(); i++) {
        v[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        v[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }
    
    for(auto g : gates) visited[g] = true;
    for(auto s : summits) visited[s] = true;
    
    for(auto g : gates) {
        for(auto s : summits) {
            dist = 10000001;
            visited[s] = false;
            dfs(g, s, 0);
            visited[s] = true;
            if ((dist < answer[1]) || ((dist == answer[1]) && (s < answer[0]))){
                answer[0] = s;
                answer[1] = dist;
            }
        }
    }
    
    return answer;
}

#include <string>
#include <vector>

using namespace std;

vector<int> answer(2, 10000001);
bool visited[50001];
int top[50001];
vector<pair<int, int>> v[50001];

void dfs(int start, int path) {
    if (path > answer[1]) return;
    if (top[start] == -1) {
        if ((path < answer[1]) || ((path == answer[1]) && (start < answer[0])))
            answer = {start, path};
        return;
    }
    
    for(auto vec : v[start]) {
        if (top[vec.first] == 1) continue;
        if ((top[vec.first] == 0) && (visited[vec.first])) continue;
        visited[vec.first] = true;
        dfs(vec.first, max(vec.second, path));
        visited[vec.first] = false;
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for(int i=0; i<paths.size(); i++) {
        v[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        v[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }
    
    fill(top, top+50001, false);
    for(auto g : gates) top[g] = 1; // 출입구
    for(auto s : summits) top[s] = -1; // 산봉우리
    
    for(auto g : gates) {
        fill(visited, visited+50001, false);
        
        dfs(g, 0);
    }
    
    return answer;
}

* BFS 반복

18번~21번 틀림

25번 시간초과

가중치 1이 아니므로 사용 불가능

O(50000 * (50000 + 200000))

#include <string>
#include <vector>
#include <queue>

using namespace std;

bool visited[50001];
int top[50001];
vector<int> answer;
vector<pair<int, int>> v[50001];

void bfs(int start) {
    queue<pair<int, int>> q;
    q.push({0, start});
    while(!q.empty()) {
        auto now = q.front();
        q.pop();

        if (top[now.second] == -1) {
            if ((now.first < answer[1]) || ((now.first == answer[1]) && (now.second < answer[0]))) answer = {now.second, now.first};
            continue;
        }
        
        for (auto i : v[now.second]) {
            if (top[i.first] == 1) continue;
            if ((top[i.first] == 0) && (visited[i.first])) continue;
            visited[i.first] = true;
            q.push({max(now.first, i.second), i.first});
        }
    }
}

vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
    for(int i=0; i<paths.size(); i++) {
        v[paths[i][0]].push_back({paths[i][1], paths[i][2]});
        v[paths[i][1]].push_back({paths[i][0], paths[i][2]});
    }
    
    fill(top, top+50001, false);
    for(auto g : gates) top[g] = 1; // 출입구
    for(auto s : summits) top[s] = -1; // 산봉우리
    answer = {50001, 10000001};
    
    for(auto g : gates) {
        fill(visited, visited+50001, false);
        bfs(g);
    }
    
    return answer;
}