[프로그래머스] 가장 먼 노드 (C++)

문제 링크: programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

1. 주의할 점

- 다익스트라 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 모든 간선에 대한 정보를 V[] 벡터에 담는다

- Check[]를 통해 1번 Node에서 부터 각 Node까지의 거리를 나타내며, 초기에 -1로 초기화한다

- 다익스트라 알고리즘을 통해 Check[] 배열을 모두 구하며, 이 과정에서 가장 먼 거리인 Longest가 초기화될 경우, Answer도 초기화한다. 만약 Longest와 같을 경우, Answer++를 수행한다

#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[20001];
int check[20001];

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    int longest=0;
    for(int i=0;i<edge.size();i++){
        int a = edge[i][0];
        int b = edge[i][1];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        check[i]=-1;
    queue<int> q;
    q.push(1);
    check[1]=0;
    while(!q.empty()){
        int cidx = q.front();
        int cv = check[cidx];
        q.pop();
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i];
            if(check[next]!=-1) continue;
            check[next]=cv+1;
            q.push(next);
            if(cv+1==longest) answer++;
            else if(cv+1>longest){
                answer=1;
                longest = cv+1;
            }
        }
    }
    return answer;
}