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

 

 

문제 파악

-주어진 2차원 배열은 서로 간선으로 연결 된 관계

-주어진 그래프에서 최대 거리에 있는 노드 갯수를 구하기

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

접근 방법

💡 -각 노드와 연결관계를 파악하고 인접리스트 형태로 변환하여 진행

-bfs 를 이용하여 해당 그래프의 순회 거리를 구하고 최대 거리의 노드 갯수 구하기

-방문 노드는 제외하고 큐 순회를 한다.

-간선 별로 몇번 째로 순회하는지 세기 위한 cnt와 직관적으로 보기 편한 리스트 구현하기

 

코드 구현

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        //인접리스트 형태로 변경
        Map<Integer,List<Integer>> graph = new HashMap<>();
        for(int[] vertex:edge){
            int f=vertex[0];int b=vertex[1];
            graph.putIfAbsent(f,new ArrayList<>());
            graph.putIfAbsent(b,new ArrayList<>());
            graph.get(f).add(b);
            graph.get(b).add(f);
        }
        Queue<int[]> que = new ArrayDeque<>();
        Map<Integer,List<Integer>> result = new HashMap<>();
        boolean[] visited = new boolean[n+1];
        int cnt=1;
        visited[1]=true;
        que.offer(new int[]{cnt,1});
        
        result.putIfAbsent(cnt,new ArrayList<>());
        result.get(cnt).add(1);//cnt에 1담기
        while(!que.isEmpty()){
            int[] connect = que.poll();
            cnt = connect[0]+1;
            int node=connect[1];
            for(int i:graph.get(node)){
                if(!visited[i]){
                    result.putIfAbsent(cnt,new ArrayList<>());
                    visited[i] = true;
                    que.offer(new int[]{cnt+1,i});
                    result.get(cnt).add(i);
                }
            }
        }
        int max=0;
        for(int i:result.keySet()){
            if(max<i) max=i;
        }
        return result.get(max).size();
    }
}

배우게 된 점

-큐에는 노드 자체를 넣고 리스트는 넣지 않는 것이 좋음

-cnt를 적절한 위치에 넣는 것이 중요

-결과를 연산하기 편하도록 리스트 만들어서 넣어두니 직관적으로 보기 편했음