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

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

문제

입출력

문제풀이

#include #include #include #include #include using namespace std; int solution(int n, vector> edge) { int answer = 0; //n개의 노드가 있는 그래프가 있습니다. //1번 노드에서 가장 멀리 떨어진 노드의 개수 구하기 //최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들 //이차원 배열이 주어지고 1번 노드에서 출발. 노드의 개수 주어짐. //[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] //1번에서 2번으로 가는 최단 경로는? //coninfo : 각 연결되어 있는 시작 노드와 끝 노드들을 넣어 연결 정보 저장 // vector> conInfo(n+1); vector distance(n+1,0);// 생성자를 이용한 선언 및 초기화 [변수이름] (개수, 값) vector visit (n+1, false); queue q; int size = edge.size(); for(int i = 0; i

(1) 주어진 이중 벡터를 재정렬하기 : conInfo

각 노드에 연결된 노드를 묶기

int size = edge.size(); for(int i = 0; i

(2) BFS

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

큐에 들어가 있는 노드를 시작노드(next_node)로 간주하고,

시작노드와 연결된 노드를 찾아서

방문 표시하고 거리 값 +1 하기

while(!q.empty()){ int startNode = q.front(); q.pop(); //start와 연결된 노드 방문 for(int i =0;i

(3) 거리 정렬한 뒤, 최대 값인 경우 answer++하기

sort(distance.begin(), distance.end()); int max_distance = distance.size(); for(int d : distance){ if(d == distance[max_distance-1]) answer++; }

from http://bohyeonstudy.tistory.com/96 by ccl(A) rewrite - 2021-08-01 15:26:52