[200425] 그래프 - 가장 먼 노드(level3)

1. 문제이해

- n개의 노드, edge 정보 배열 --> 1번 노드로부터 가장 먼 노드 몇 개?

- 1번 노드와의 최단 거리구한 후 이 중 최대값 선택 --> 이 최대값을 가지는 노드의 개수

 

2. 전략

① edgeMap(HashMap<Integer, ArrayList<Integer>>) : 각 노드별 연결된 노드(일종의 인접리스트)

② resultMap(HashMap<Integer, Integer>) : 도달한 노드의 index와 거리 정보

③ BFS : resultMap에 모든 노드가 들어갈 때까지 BFS!!

- **BFS이므로 Queue를 이용한다. 시작노드 선정 기준

- resultMap에 없는 경우만 put해준다. 이 때 max값 함께 갱신.

④ resultMap에서 max와 같은 값을 가진 노드의 개수 출력

 

3. 참고사항

BFS(Breadth First Search) : 너비 우선 탐색

- 큐를 이용하여 그 다음 탐색할 노드를 선정한다.

- 인접행렬 혹은 인접리스트를 가지고 탐색

- 방문 여부를 기록하는 boolean[] 배열을 이용.(이 문제에서는 resultMap)

- 모든 노드를 탐색하는 경우라면 큐가 빌 때까지 반복한다.

 

4. 코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        //노드 - 연결된 노드들 리스트
        HashMap<Integer, ArrayList<Integer>> edgeMap = new HashMap<>();
        for(int i = 1; i <= n; i++){
            edgeMap.put(i, new ArrayList<Integer>());
        }
        for(int i = 0; i < edge.length; i++){
            edgeMap.get(edge[i][0]).add(edge[i][1]);
            edgeMap.get(edge[i][1]).add(edge[i][0]);
        }
        int max = 0;
        HashMap<Integer, Integer> resultMap = new HashMap<>(); //도달한 노드
        //BFS로 SEARCH!!! - 큐 이용
        Queue<Integer> q = new LinkedList<>(); 
        q.add(1); resultMap.put(1, 0);
        while(resultMap.size() < n){
            int target = q.poll();
            for(int e : edgeMap.get(target)){
                if(!resultMap.containsKey(e)){
                    resultMap.put(e, resultMap.get(target)+1);
                    q.add(e);
                    if(max < resultMap.get(target) + 1) max = resultMap.get(target) + 1;
                }
            }
        }
        for(int key : resultMap.keySet()){
            if(resultMap.get(key) == max)   answer++;
        }
        return answer;
    }
}