프로그래머스 : 가장 먼 노드

풀이 :

 

입출력 예

n                                                      vertex                                         return

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

 

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

 

1이랑 연결 된걸 삭제  , next 큐 = { 3,2}

[[3, 6], [4, 3], [3, 2], [2, 4], [5, 2]]

 

2,3이랑 연결 된걸 삭제  , next 큐 = { 6,4,5}

 

--> 6,4,5 가 가장 먼 노드 이다.

 

갯수는 3

 

---

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
bool v[20001];
int solution(int n, vector<vector<int>> edge) {
    int ans = -1;
    queue<int> q;
    queue<int> nq;
    q.push(1);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i=0; i<edge.size(); i++){
            if(now == edge[i][0] ||now ==edge[i][1]){
                if(now!=edge[i][0]){
                    if(v[edge[i][0]]==false){
                        v[edge[i][0]] = true;
                        nq.push(edge[i][0]);
                    }
                }else{
                    if(v[edge[i][1]]==false){
                        v[edge[i][1]] = true;
                        nq.push(edge[i][1]);
                    }
                }
                edge.erase(edge.begin()+i);
                i--;
            }
        }
        if(q.empty()){
            q=nq;
            if(!nq.empty()){
                ans = nq.size();
            }
            queue<int> empty;
            nq = empty;
        }
    }
    
    return ans;
}