가장 먼 노드

문제 링크

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

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

 

문제 풀이 코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

const int MN = 20001;

bool graph[MN][MN];
bool visited[MN];

vector<vector<int>> ans;

int BFS(int n){
    queue<int> q; //Queue 생성
    q.push(1); // 초기 시작점
    visited[1]= true;
    
    int level=0;    
    while(!q.empty()){
        int qSize=q.size(); 
        vector <int> a;
        for(int s=0; s<qSize; s++){//level을 측정하기 위한 반복문
            int cur=q.front();
            q.pop();

            for(int i=1; i<=n; i++){
                if(graph[cur][i]&&!visited[i]){
                    a.push_back(i);
                    visited[i]=true;
                    q.push(i);
                }
            }
        } ans.push_back(a);
        level++; 
    }
    
    ans.pop_back();
    
    return ans[ans.size()-1].size();
}

int solution(int n, vector<vector<int>> edge) {
    
    int answer = 0;
    
    for(int i=0; i<edge.size(); i++){
        
        int u=edge[i][0];
        int v=edge[i][1];
        
        //양방향 그래프이기 때문에
        graph[u][v]=true; graph[v][u]=true;
    
    }
    
    answer=BFS(n);
    
    return answer;
}

탐색을 하면서 그래프의 레벨(시작 정점으로부터의 길이)을 측정하기 위해 Queue의 크기를 측정하고 그만큼 반복문을 돌렸다.