프로그래머스 49189 가장 먼 노드 자바 풀이

난이도 : Lv. 3

풀이일 : 2410211

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

프로그래머스

---

문제

---

풀이

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int[] distance = new int[n];
        boolean [][] loads = new boolean[n][n];
        int maxi = 0;
        
        // 연결 정보 저장
        for (int i = 0; i < edge.length; i++) {
            loads[edge[i][0] - 1][edge[i][1] - 1] = true;
            loads[edge[i][1] - 1][edge[i][0] - 1] = true;
        }
        
        // 거리 조사 준비
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        distance[0] = 1;
        
        while (!queue.isEmpty()) {
            int x = queue.poll();
            
            // X와 연결되어 있는 미방문 노드를 찾아 거리 기록
            for (int k = 0; k < n; k++) {
                if (loads[x][k] && distance[k] == 0) {
                    distance[k] = distance[x] + 1;
                    
                    // 최대 거리 갱신
                    if (maxi < distance[x] + 1) {
                        maxi = distance[x] + 1;
                    }
                    queue.add(k);
                }
            }
        }
        
        // 최대 거리 노드 수 세기
        for (int i = 0; i < n; i++) {
            if (distance[i] == maxi) {
                answer++;
            }
        }
        return answer;
    }
}

• edge를 순회하며 연결 정보를 2차원 배열 loads에 표시해준다.
• 노드별 거리 탐색을 위한 queue를 생성한다.
• 큐에 요소가 들어있는 동안, 현재 노드에서 연결된 노드 중 아직 방문하지 않은 노드를 찾아 거리를 기록한다.
• 새로 거리를 기록한 노드가 최대거리보다 크다면, 최대거리를 갱신한다.
• 새로 거리를 기록한 노드를 큐에 추가하여 반복한다.
• while 반복문을 종료한 후, distance를 순회하며 최댓값들의 개수를 answer에 반영한다.

---

느낀점

• 파이썬이었다면, loads를 [[], []] 형태로 만들어, 연결된 노드를 리스트에 추가했을 텐데, 자바에 익숙하지 않아서 boolean 2차원 배열을 사용하였다.
• 파이썬이었다면, 최대 거리 노드 수 세기도 배열에서 특정 요소의 개수를 세는 메서드를 사용했을텐데, 자바라서 그냥 반복문을 돌리면서 셌다.
• 자바는 다른 사람들 풀이 코드를 좀 찾아보고 더 효율적인 방식을 배우는 시간이 필요할 것 같다.