LEVEL 3 : 가장 먼 노드

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

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

 

• 문제

  • 

    문제

  • 

    예시

---

풀이

• 그래프 탐색 문제이다.
• 1번 노드부터 시작하여 가장 멀리 있는 노드의 개수의 숫자를 세어야 된다.
• 시작 노드가 정해져 있고 그중 가장 멀리 있는 노드를 구하는 거므로 다익스트라 알고리즘을 활용한다.
  • List형 배열을 노드의 개수만큼 생성 후 초기화한다.
  • 간선의 돌면서 간선을 노드를 연결하여 준다.
    • 실제 노드의 번호는 edge에 나온 정보보다 1 값 작으므로 start-1, end-1을 해준다.
    • 문제의 조건의 보면 간선은 양방향이라고 나와 있으므로 반대에서도 연결을 해준다.
  • 다익 스트라 알고리즘 실행
    • 모든 최소 경로의 값을 최댓값으로 설정한 뒤, 시작 위치의 node값을 0으로 세팅한다.
    • 연결된 node를 돌며 다음 노드의 경로 값이 > 현재 노드의 경로 + 1 값 보다 클 경우 다음 노드의 값을 현재 노드의 경로 + 1로 바꿔준다(최소 경로)
  • 경로 값을 모두 구한 뒤 최대 경로 값과 같은 개수를 count 해준다

• public static int[] dist;
  public static int solution(int n, int[][] edge) {
          int answer = 0;
          List<Integer>[] map = new ArrayList[n];//List형 배열 생성
          for(int i=0;i<n;++i) {
           map[i] = new ArrayList<>();//배열 초기화
          }
          for(int i=0;i<edge.length;++i) {
           int start = edge[i][0]-1;//노드의 인덱스는 번호 - 1 값이기 때문에 -1 해준다
           int end = edge[i][1]-1;
           map[start].add(end);//양방향 이라서 시작 위치-종료 위치 , 종료 위치-시작 위치 둘 다 연결해줘야 된다
           map[end].add(start);
          }
          dijkstra(map,n);//다익스트라 알고리즘 시작
          int max = Arrays.stream(dist).max().getAsInt();// 1번 노드부터 모든 노드로 가는 최소 경로 값을 구했으므로 이중 최댓값을 개수를 counting 한다.
          for(int i=0;i<dist.length;++i) {
           if(max == dist[i])
           answer++;
          }
          return answer;
      }
  private static void dijkstra(List<Integer>[] map, int n) {
    Queue<Integer> que = new LinkedList<>();
    dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);// 최소 경로의 모든 값을 INT 형의 최댓값으로 세팅
    dist[0] = 0;//시작 노드 값의 최소 경로 값을 0으로 설정
    que.offer(0);
    while(!que.isEmpty()) {
      int now = que.poll();
      for(int next : map[now]) {
     		if(dist[next] > dist[now] + 1) {//다음 노드의 최소 경로 값이 현재 노드 최소 경로 + 1 보다 크면
      		dist[next] = dist[now] + 1;//다음 노드의 최소 경로 값을 현재 노드 최소경로 +1로 변경한 뒤 que에 넣는다
      		que.offer(next);
    		}
  	}
    }
  }