가장 먼 노드

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

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

<C++>

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;

int bfs( vector<vector<int>>&vlist, int target,int n){
    
    queue<int>q;
    vector<int>m(n+1,0);
    q.push(1);
    m[1]=0;
    while(!q.empty()){
        int vertex= q.front();
        q.pop();
        for(int i=0; i<vlist[vertex].size(); i++){
            
        if(m[vlist[vertex][i]]==0 && vlist[vertex][i]!=1){
            q.push(vlist[vertex][i]);
            m[vlist[vertex][i]]=m[vertex]+1;
            if(vlist[vertex][i]==target){return m[vlist[vertex][i]];}
        }
        }
    }
    
}

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    vector<vector<int>>vlist(20001);
    priority_queue<int>pq;

    for(int i=0; i<edge.size(); i++){
        vlist[edge[i][0]].push_back(edge[i][1]);
        vlist[edge[i][1]].push_back(edge[i][0]);
    }
    
    for(int i=2; i<=n; i++){
        int res = bfs(vlist,i,n);
        pq.push(res);
     }
    
    int maxnum = pq.top();
    answer++;
    pq.pop();
    while(pq.top()==maxnum){
        answer++;
        pq.pop();
    }
    
    return answer;
}

 

<java>

import java.util.*;
class Solution {
    
    class Pair{
        int x; int y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
        int getx(){
            return x;
        }
        int gety(){
            return y;
        }
        
    }
    
    public int bfs(ArrayList<ArrayList<Integer>>arr,int[] chk){
        
        Queue<Pair>q = new LinkedList<>();
        q.add(new Pair(1,0));
        
        int mx =0;
        int cnt =0;
        
        chk[1]=1;
        
        while(!q.isEmpty()){
            
            Pair p = q.peek();
            q.poll();
            
            int k = p.getx();
            int l = p.gety();
            
            if(mx<l){mx=l; cnt=1;}
            else if(mx==l){cnt++;}
            
           // System.out.println("k:"+k);
           // System.out.println(cnt);
            
            for(int i=0; i<arr.get(k).size(); i++){
               int nk = arr.get(k).get(i); // 
                if(chk[nk]==0){
                    q.add(new Pair(nk,l+1));
                    chk[nk]=1;
                }
            }
        }
        return cnt;
        
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        int[] chk = new int[n+1];
        
        /*자바에서 인접리스트 구하는 법*/
        ArrayList<ArrayList<Integer>>a = new ArrayList<>();
        
        for(int i=0; i<=n; i++){
            a.add(new ArrayList<Integer>());
        }

        for(int i=0; i<edge.length; i++){
            a.get(edge[i][0]).add(edge[i][1]);
            a.get(edge[i][1]).add(edge[i][0]);
         }
        
        answer = bfs(a,chk);
        
        
        return answer;
    }
}