프로그래머스 - 가장 먼 노드

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

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

 

• 가장 먼 노드의 갯수를 출력해야 하기 때문에 모든 노드를 방문해야지 풀 수 있다.
  • 노드 방문 시 해당 노드의 깊이와 최대 깊이를 비교
  • 모든 노드 방문 후 최대 깊이로 노드 개수 출력
  • BFS와 인접 리스트를 활용하여 문제를 풀었음.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

class Solution {

    private boolean[] visited;
    private ArrayList<Integer>[] adj;

    public int solution(int n, int[][] edge) {
        //초기화
        visited = new boolean[n + 1];
        adj = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < edge.length; i++) {
            int origin = edge[i][0];
            int dest = edge[i][1];
            adj[origin].add(dest);
            adj[dest].add(origin);
        }

        Queue<State> bfs = new LinkedList<>();
        bfs.add(new State(1, 1));
        List<State> visitedNode = new ArrayList<>();

        int maxDepth = -1;
        while (!bfs.isEmpty()) {
            State currentNode = bfs.poll();
            if (visited[currentNode.nodeIndex]) continue;
            visited[currentNode.nodeIndex] = true;
            visitedNode.add(currentNode);

            //노드 방문 시 깊이와 최대 깊이 정보를 비교하여 갱신
            if (currentNode.depth > maxDepth) {
                maxDepth = currentNode.depth;
            }

            for (int i = 0; i < adj[currentNode.nodeIndex].size(); i++) {
                bfs.add(new State(adj[currentNode.nodeIndex].get(i), currentNode.depth + 1));
            }
        }

        final int max = maxDepth;
        int maxLengthCount = visitedNode.stream().filter(node -> node.depth == max).collect(Collectors.toList()).size();

        return maxLengthCount;
    }
}

//방문 노드의 정보를 저장
class State {
    public final int nodeIndex;
    public final int depth;

    public State(int nodeIndex, int depth) {
        this.nodeIndex = nodeIndex;
        this.depth = depth;
    }
}