[L3] 프로그래머스 가장 먼 노드 C++ 다익스트라, 최단 경로

리뷰

프로그래머스

 

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하는 문제

다익스트라로 모든 노드까지의 최단 거리를 구한 후, 해당 노드 중 거리가 최대값인 노드를 찾는다.

최대값과 동일한 값을 같는 거리를 가진 노드의 개수를 출력해 주었다.

 

 

전역 변수

• nodes : 노드의 개수를 저장할 변수
• lst : 노드간 인접 리스트를 저장할 정수형 벡터 배열, 노드의 최대 갯수인 2만보다 크게 해주어야 한다.
• Pos : 다익스트라의 탐색용 구조체, 우선순위 큐용 오름차순 cmp함수를 정의했다.

 

함수

1. dijkstra

int dijkstra()

 

1번 노드로부터 모든 노드까지의 거리를 구하고, 최대 거리를 가진 노드의 개수를 리턴하는 함수

1. Pos타입의 우선순위 큐 pq를 초기화 하고, 1, 0값을 push해준다.
2. nodes + 1크기의 정수형 벡터 dist를 초기화 하고 내부 값은 10억으로 넣어준다.
3. 1번 노드의 dist값을 0으로 초기화 해준다.
4. pq가 빌때까지 while문을 실행하고 가장 top에 있는 원소를 꺼내어 준다.
5. 해당 노드의 인접 리스트를 순회한다.
6. 다음 노드의 길이가 현재 노드의 길이 + 1보다 크다면 값을 갱신해주고 pq에 다음 노드와 신규 거리를 추가해준다.
7. while문이 종료되었다면, dist벡터 내에 존재하는 최대값을 찾아준다.
8. count메서드를 통해 해당 값을 같은 원소의 개수를 리턴해 준다.

 

문제풀이

1. nodes에 n값을 저장해준다.
2. edge벡터를 순회하며 간선 정보를 lst벡터에 양방향 간선으로 추가해준다.
3. dijkstra함수를 호출하여 탐색을 마치고 나온 리턴값을 리턴해준다.

 

참고 사항

• 입력은 단방향 간선으로 주어진다, 해당 간선을 양방향 간선으로 치환해 주어야 한다.
• 노드의 번호는 1-based-index이므로 모든 노드를 순회할 때는 1 ~ nodes 범위로 탐색해 주어야 한다.
• dist또한 마찬가지로 nodes + 1개로 초기화 해주고, max값을 찾을땐 0번 노드를 제외해야한다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int nodes;
vector<int> lst[20001];

struct Pos {
    int cn, cd;
    bool operator<(const Pos& other) const {
        return cd > other.cd;
    }
};

int dijkstra() {
    priority_queue<Pos> pq;
    pq.push({1, 0});
    vector<int> dist(nodes + 1, 1e9);
    dist[1] = 0;
    
    while (!pq.empty()) {
        Pos pos = pq.top(); pq.pop();
        int cn = pos.cn, cd = pos.cd;
        
        for (int nn : lst[cn]) {
            if (dist[nn] > cd + 1) {
                dist[nn] = cd + 1;
                pq.push({nn, cd + 1});
            }
        }
    }
    int max_val = 0;
    for (int i = 1; i < nodes + 1; i++) {
        if (dist[i] != 1e9) max_val = max(max_val, dist[i]);
    }

    return count(dist.begin() + 1, dist.end(), max_val);
}

int solution(int n, vector<vector<int>> edge) {
    nodes = n;
    for (const auto& e : edge) {
        lst[e[0]].push_back(e[1]);
        lst[e[1]].push_back(e[0]);
    }
    return dijkstra();
}