[프로그래머스] 가장 먼 노드

[프로그래머스] 가장 먼 노드

문제

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

N개의 노드 중 1번 노드와 가장 먼 거리의 노드수를 구하는 문제

문제 풀이

시작점이 정해져있고 최단거리로 이동할 경우 가장 먼 거리를 파악해야 한다.

1번 노드로부터 다익스트라 수행 후 가장 먼 거리를 가진 노드들의 수를 카운트하여 return 한다.

소스 코드

#include #include #include const int MAX_N = 20001; const int MAX_M = 50000; using namespace std; int solution(int n, vector> edge) { vector adj[MAX_N]; int d[MAX_N]; int answer = 0; int maxDist = -1; // 인접리스트 for(int i = 0; i < edge.size(); i++){ int from = edge[i][0], to = edge[i][1]; adj[from].push_back(to); adj[to].push_back(from); } // 초기화 for(int i = 2; i <= n; i++) d[i] = MAX_M + 1; // 다익스트라 priority_queue> q; q.push({0,1}); while(!q.empty()){ int curNode = q.top().second; int curDist = -q.top().first; q.pop(); if(d[curNode] < curDist) continue; for(int i = 0; i < adj[curNode].size(); i++){ int nextNode = adj[curNode][i]; if(d[nextNode] <= d[curNode] + 1) continue; d[nextNode] = d[curNode] + 1; // 가장 먼 거리 maxDist = maxDist < d[nextNode] ? d[nextNode] : maxDist; q.push({-(d[nextNode]), nextNode}); } } for(int i = 1; i <= n; i++) if(d[i] == maxDist) answer++; return answer; }

from http://wjdgus2951.tistory.com/107 by ccl(A) rewrite - 2021-08-24 22:26:44