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

문제

입출력

문제풀이

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
int solution(int n, vector<vector<int>> 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<vector<int>> conInfo(n+1);
    vector<int> distance(n+1,0);// 생성자를 이용한 선언 및 초기화 [변수이름] (개수, 값)
    vector <bool> visit (n+1, false);
    queue<int> q; 
    int size = edge.size();
    for(int i = 0; i<size;i++){
        int start = edge[i][0];
        int end = edge[i][1];
        conInfo[start].push_back(end);
        conInfo[end].push_back(start);
    }
    //각 노드[] 에 연결된 노드들을 순서없이 넣었음.
    //1번을 방문한 것들을 이용하나?
    //1번 배열에 들어간 것들을 먼저 확인?
    //그 후에는 1번 노드에서 가장 먼 노드를 알아야 하고 그 개수를 알아야 한다. 
    //그래서 큐를 이용한다.
    //bfs
    
    q.push(1);
    visit[1] = true;
    //큐에 넣고 방문 표시하기 
    while(!q.empty()){
        int startNode = q.front();
        q.pop();
        //start와 연결된 노드 방문
        for(int i =0;i<conInfo[startNode].size();i++){
            int endNode = conInfo[startNode][i];
            //방문하기 전에 전에 방문을 했는지 조건 달고 방문표시
            if(!visit[endNode]){
                
                visit[endNode] = true;
                //거리 값 정리. 
                distance[endNode] = distance[startNode] +1;//?????????
                q.push(endNode);
            }
        }
        //거리 정렬하기 
    }
        sort(distance.begin(), distance.end());
        int max_distance  = distance.size();
        for(int d : distance){
            if(d == distance[max_distance-1])
                answer++;
        }
    return answer;
}

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

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

    int size = edge.size();
    for(int i = 0; i<size;i++){
        int start = edge[i][0];
        int end = edge[i][1];
        conInfo[start].push_back(end);
        conInfo[end].push_back(start);
    }

(2) BFS

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

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

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

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

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

    while(!q.empty()){
        int startNode = q.front();
        q.pop();
        //start와 연결된 노드 방문
        for(int i =0;i<conInfo[startNode].size();i++){
            int endNode = conInfo[startNode][i];
            //방문하기 전에 전에 방문을 했는지 조건 달고 방문표시
            if(!visit[endNode]){
                
                visit[endNode] = true;
                //거리 값 정리. 
                distance[endNode] = distance[startNode] +1;//?????????
                q.push(endNode);
            }
        }
        //거리 정렬하기 
    }

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

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