[Programmers] 가장 먼 노드

난이도 : Level 3

문제링크

• 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하라

 

해설

1. 인접노드 데이터 자료구조 생성

private Map<Integer, Set<Integer>> init(int[][] edge, Map<Integer, Set<Integer>> edges) {
    for (int i = 0; i < edge.length; i++) {
        int src = edge[i][0]-1, desc = edge[i][1]-1;
        makeEdges(src, desc, edges);
        makeEdges(desc, src, edges);
    }

    return edges;
}

private void makeEdges(int src, int desc, Map<Integer, Set<Integer>> edges) {
    if (!edges.containsKey(src)) {
        Set<Integer> set = new HashSet<>();
        set.add(desc);
        edges.put(src, set);
    } else {
        edges.get(src).add(desc);
    }                
}

• 인접노드의 정보가 담긴 Map 자료구조를 생성함
  • Key : 시작 노드, Value : 인접노드들의 집합

 

2. 너비우선 탐색으로 가장 먼 거리 구하기

public int solution(int n, int[][] edge) {
    int answer = 0, longestDist = 0;
    Map<Integer, Integer> map = new HashMap<>();
    Map<Integer, Set<Integer>> edges = init(edge, new HashMap<>());        

    boolean[] visited = new boolean[n];
    visited[0] = true;

    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[] {0, 0});

    while (!queue.isEmpty()) {
        int[] c = queue.poll();
        int cp = c[0], ct = c[1];   

        for (int neignbor : edges.get(cp)) {
            if (visited[neignbor]) continue;
            int np = neignbor, nt = ct+1;
            if (!map.containsKey(nt)) map.put(nt, 1);
            else map.put(nt, map.get(nt)+1);

            longestDist = nt;

            visited[neignbor] = true;
            queue.offer(new int[] {np, nt});
        }            
    }

    return map.get(longestDist);
}

 

• 1과의 거리별 존재하는 노드수를 Map 자료구조에 저장하기
• 너비우선 탐색으로 방문하지 않은 이웃을 방문하고, 1과의 거리 별 카운트 수를 한개씩 올린다.