C++ / 프로그래머스 / 가장 먼 노드

문제

 

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

프로그래머스

문제풀이

 

문제를 보자마자 두 가지 방법이 생각났다. 

하나는 BFS를 이용한 풀이고, 다른 하나는 다익스트라 알고리즘을 이용한 풀이이다.

이번 풀이에서는 다익스트라 알고리즘을 사용했다.

 

문제를 보면 1번 노드에서 가장 먼 노드를 구해야 한다.

간선은 양방향 간선이므로 주어진 배열을 가지고 따로 (n+1) * (n+1)크기의 벡터를 만들어 연결이 되면 1을 저장한다.

(1번 노드부터 시작하므로 편의성을 위해 노드보다 하나 더 큰 사이즈로 만듦)

 

다익스트라의 기본 틀과는 크게 다르지 않다.

다만 가장 먼 노드의 개수를 구해야 하므로 우선순위 큐가 비어 반복문이 종료되었다면,  최댓값보다 큰 값이 나오면 갱신하고 개수를 초기화한다.

최댓값과 같은 값이 나오면 개수를 늘리면 된다.

 

 

코드

#include <vector>
#include <queue>
#include <algorithm>
#define MAX 50001
using namespace std;

int node_cnt, answer;
vector<vector<bool>>graph;

void Dijkstra(int start_node) {
    int next(0), node(0), dist(0), n_dist(0), max_dist(0);
    priority_queue<pair<int, int>>pq;
    vector<int>dist_v(node_cnt + 1, MAX);
    dist_v[start_node] = 0;
    pq.push({ 0, start_node });

    while (!pq.empty()) {
        dist = -pq.top().first;
        node = pq.top().second;
        pq.pop();

        for (next = 1; next <= node_cnt; ++next) {
            n_dist = graph[node][next];
            if (n_dist == 0) continue;
            if (dist_v[next] > dist + n_dist) {
                dist_v[next] = dist + n_dist;
                pq.push({ -dist_v[next], next });
            }
        }
    }
    for (next = 1; next <= node_cnt; ++next) {
        if (max_dist < dist_v[next]) {
            answer = 1;
            max_dist = dist_v[next];
        }
        else if (max_dist == dist_v[next]) {
            answer++;
        }
    }
}

int solution(int n, vector<vector<int>> edge) {
    int idx(0), idx2(0);
    node_cnt = n;
    graph = vector<vector<bool>>(n + 1, vector<bool>(n + 1, false));

    for (idx = 0; idx < edge.size(); ++idx) {
        graph[edge[idx][0]][edge[idx][1]] = 1;
        graph[edge[idx][1]][edge[idx][0]] = 1;
    }

    Dijkstra(1);

    return answer;
}