프로그래머스 가장 먼 노드

문제

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

코드

#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<pair<int, int>>> graph(n+1);
    priority_queue<pair<int, int>> pq;
    vector<int> table(n+1,1e9);

    for (auto i : edge){
        graph[i[0]].push_back({1, i[1]});
        graph[i[1]].push_back({1, i[0]});
    }

    pq.push({ 0,1 });
    table[1] = 0;
    int maxN = 0;
    while (!pq.empty()){
        int d = -pq.top().first;
        int num = pq.top().second;
        pq.pop();

        if (table[num] < d) continue;

        for (int i = 0; i < graph[num].size(); i++){
            int cost = d + graph[num][i].first;

            if (cost < table[graph[num][i].second]){
                table[graph[num][i].second] = cost;
                pq.push({-cost, graph[num][i].second});
                maxN = max(maxN, cost);
            }
        }
    }
    for (int i : table){
        if (i == maxN)
            answer++;
    }
    return answer;
}

풀이

처음에는 인접행렬로 그래프를 구현해서 풀려고 했습니다 근데 테스트 케이스 7,8,9번에서 시간초과가 나오더라고요

인접행렬 코드

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

using namespace std;

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int maxValue=0;
    vector<vector<int>> graph(n,vector<int>(n,0));
    for(auto i:edge){
        graph[i[0]-1][i[1]-1]=-1;
        graph[i[1]-1][i[0]-1]=-1;
    }
    for(int i=0;i<n;i++) graph[i][i]=-1;
    
    queue<vector<int>> q;
    q.push({0,0,1});
    while(!q.empty()){
        int y=q.front()[0];
        int x=q.front()[1];
        int dist=q.front()[2];
        maxValue=max(maxValue,dist);
        q.pop();
        
        for(int i=0;i<n;i++){
            if(graph[y][i]==-1){
                graph[y][i]=dist;
                q.push({y,i,dist+1});
            }
            if(graph[i][x]==-1){
                graph[i][x]=dist;
                q.push({i,x,dist+1});
            }
        }  
    }

    for(int i=0;i<n;i++){
        if(graph[i][i]==maxValue-1)answer++;
    }
    return answer;
}

그래프를 구현하는 방법이 대표적으로 인접행렬과 인접리스트 방식이 있는데 인접행렬 방식은 노드의 개수가 많아질수록 메모리의 양과 탐색하는데 걸리는 시간이 제곱으로 늘어납니다 인접리스트 방식으로 그래프를 구현해준뒤에 풀면 됩니다 저는 모든 간선의 비용이 1이라고 생각한 뒤에 다익스트라 알고리즘을 사용해서 풀었습니다.