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

문제

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

프로그래머스

 

코드

자바

import java.util.*;

class Edge implements Comparable<Edge> {
    public int vex;
    public int cost;
    
    public Edge(int vex, int cost) {
        this.vex = vex;
        this.cost = cost;
    }
    
    @Override
	public int compareTo(Edge ob) {
		return this.cost - ob.cost;
	}
}

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[1] = 0;
        
        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.offer(new Edge(1, 0));
        
        while (!pQ.isEmpty()) {
            Edge tmp = pQ.poll();
            if (distance[tmp.vex] >= tmp.cost) {
                System.out.println(tmp.vex);
                for (int nv : graph.get(tmp.vex)) {
                    if (distance[nv] > tmp.cost + 1) {
                        distance[nv] = tmp.cost + 1;
                        pQ.offer(new Edge(nv, distance[nv]));
                    }
                }
            }
        }
        
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < distance.length; i++) {
            max = Math.max(max, distance[i]);
        }
        
        int answer = 0;
        for (int i = 1; i < distance.length; i++) {
            if (distance[i] == max)
                answer++;
        }
        
        return answer;
    }
}

파이썬

import heapq
INF = int(1e9)

def solution(n, edge):
    graph = [[] for _ in range(n + 1)]
    distance = [INF] * (n + 1)
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    queue = []
    heapq.heappush(queue, (0, 1))
    distance[1] = 0
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + 1
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(queue, (cost, i))
                
    return len([i for i in distance if i == max(distance[1:])])