(Python, Java) 프로그래머스 - 가장 먼 노드

23 Feb 2022 in Algorithm on Programmers, Level3

[문제 링크]

Python 풀이

from collections import deque
from collections import Counter


def solution(n, edge):
    graph = [[] for _ in range(n + 1)]

    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)

    distance = bfs(graph, n)

    return Counter(distance)[max(distance)]


def bfs(graph, n):
    distance = [-1] * (n + 1)
    distance[1] = 0
    q = deque()
    q.append([1, 0])  # pos, cost

    while q:
        cur, cost = q.popleft()

        for next in graph[cur]:
            if distance[next] == -1:
                distance[next] = cost + 1
                q.append([next, cost + 1])
    return distance

범위가 크기 때문에 플로이드 워셜은 안되고 BFS나 다익스트라로 해결할 수 있다.
이동 거리 비용이 1이므로 BFS를 사용해서 해결했다.

Java 풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        Map<Integer, List<Integer>> graph = initGraph(edge);
        int[] distance = bfs(graph, n);
        return calculateMaxCount(distance);
    }

    private Map<Integer, List<Integer>> initGraph(int[][] edge) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] pos : edge) {
            List<Integer> next = graph.getOrDefault(pos[0], new ArrayList<>());
            next.add(pos[1]);
            graph.put(pos[0], next);

            next = graph.getOrDefault(pos[1], new ArrayList<>());
            next.add(pos[0]);
            graph.put(pos[1], next);
        }
        return graph;
    }

    private int[] bfs(Map<Integer, List<Integer>> graph, int n) {
        int[] distance = new int[n + 1];
        Arrays.fill(distance, -1);
        distance[1] = 0;

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0));

        while (!q.isEmpty()) {
            Node node = q.poll();
            for (Integer next : graph.get(node.pos)) {
                if (distance[next] == -1) {
                    distance[next] = node.cost + 1;
                    q.add(new Node(next, distance[next]));
                }

            }
        }
        return distance;
    }

    private int calculateMaxCount(int[] distance) {
        int count = 0;
        int maxDistance = Arrays.stream(distance).max().getAsInt();
        for (int d : distance) {
            if (d == maxDistance)
                count++;
        }
//        int maxDistance = Arrays.stream(distance).max().getAsInt();
//        return (int)Arrays.stream(distance).filter(d -> d == maxDistance).count();
        
        return count;
    }

    private class Node {
        int pos;
        int cost;

        public Node(int pos, int cost) {
            this.pos = pos;
            this.cost = cost;
        }
    }
}