[프로그래머스] 가장 먼 노드 (파이썬 & 자바)

📕 문제

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

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

 

💡 풀이법

-Python

from collections import defaultdict, deque
def solution(n, edge):
    def bfs():
        nonlocal min_dists
        deq = deque([(1,0)])
        
        while deq:
            m, d = deq.popleft()

            for v in graph[m]:
                if min_dists[v-1] == 0:
                    min_dists[v-1] = d+1
                    deq.append([v, d+1])

    graph = defaultdict(list)
    for e in edge:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])

    min_dists = [1] + [0 for _ in range(n-1)]
    bfs()
    answer = min_dists[1:].count(max(min_dists))
    return answer

 

-Java

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<ArrayList<Integer>> graph=new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<edge.length;i++){
            graph.add(new ArrayList<Integer>());
        }

        for(int[] node:edge){
            graph.get(node[0]).add(node[1]);
            graph.get(node[1]).add(node[0]);
        }
        
        int[] minDists = new int[n+1];
        minDists[1] = 1;
        
        Queue<Integer> q=new LinkedList<>();
        q.add(1);
        
        while (!q.isEmpty()) {
            int m = q.poll();
            
            for(int v:graph.get(m)){
                if(minDists[v] == 0){
                    minDists[v]=minDists[m]+1;
                    q.add(v);
                }
            }
        }
        int answer = 0;
        int max_dist = 0;
        
        for(int d:minDists){
            if (max_dist<d) {
                max_dist=d;
                answer = 1;
            } else {
                if (max_dist==d) {
                    answer++;
                }
            }
        }

        return answer;
    }
}