Today's Algorithm(2019-01-28)

programmers. 가장 먼 노드

그래프 문제이지만 bfs의 개념을 알면 쉽게 풀 수 있는 문제였습니다. 다만 기초적인 bfs에서 조금 더 나아가 length를 따로 표시해줘야한다는 점에서 좀 더 추가적으로 구현해야 합니다. 왜냐하면 length가 몇이냐에 따라서 answer값이 계속 갱신되어야 하기 때문입니다.

 

기본적인 아이디어는 bfs로 풀면서 최단 거리를 찾아나갑니다. 그리고 Queue에서 Node(해당 노드의 수, length 상태값을 가짐)를 꺼낼 때 count하고 있는 length의 값과 같으면(같은 길이의 노드일때) answer을 증가시키고, count하고 있는 length가 아니면(더 큰 길이의 노드일때) answer = 1 로 초기화시킵니다.

 

class Solution {
    public int solution(int n, int[][] edge) {
        int length = 0;
        int answer = 0;
        Map<Integer, List<Integer>> map = init(edge);
        Queue<Node> queue = new LinkedList<>();
        boolean[] visit = new boolean[n + 1];

        visit[1] = true;
        queue.add(new Node(1, 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int nNum = node.num;
            int nLength = node.length;

            if (nLength == length) answer++;
            else {
                length = nLength;
                answer = 1;
            }

            for (Integer integer : map.getOrDefault(nNum, new ArrayList<>())) {
                if (!visit[integer]) {
                    queue.add(new Node(integer, nLength + 1));
                    visit[integer] = true;
                }
            }
        }

        return answer;
    }

    public Map<Integer, List<Integer>> init(int[][] edge) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] ints : edge) {
            int num1 = ints[0];
            int num2 = ints[1];
            List<Integer> values = map.getOrDefault(num1, new ArrayList<>());
            List<Integer> values2 = map.getOrDefault(num2, new ArrayList<>());
            values.add(num2);
            values2.add(num1);
            map.put(num1, values);
            map.put(num2, values2);
        }
        return map;
    }
}

class Node {
    int num;
    int length;

    public Node(int num, int length) {
        this.num = num;
        this.length = length;
    }
}