[Java] 프로그래머스 - 가장 먼 노드 (3단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	△
본인의 실력으로 풀었는가?	O

 

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

 

 

 

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int position = 0;
        
        Node[] list = new Node[n+1];
        for (int i = 1; i < list.length; i++) {
            list[i] = new Node();
        }
        
        for(int i = 0; i < edge.length; i++) {
            int a = edge[i][0];
            int b = edge[i][1];
            
            Node node1 = list[a];
            Node node2 = list[b];
            
            node1.addNode(b);
            node2.addNode(a);
        }
        
        Queue<Integer> q = new LinkedList<>();
        list[1].far = 0;
        q.add(1);
        while (!q.isEmpty()) {
            int num = q.poll();
            Node node = list[num];
            
            int far = node.far;
            ArrayList<Integer> arr = node.arr;
            
            for (int i = 0; i < arr.size(); i++) {
                int lNum = arr.get(i);
                Node temp = list[lNum];
                if (temp.far != -1) continue;
                
                temp.far = far + 1;
                if (position < far+1) {
                    position = far+1;
                    answer = 1;
                } else if (position == far+1) {
                    answer++;
                }
                
                q.add(lNum);
            }
        }
        
        return answer;
    }
    
    class Node {
        ArrayList<Integer> arr;
        int far = -1;
        public Node() {
            arr = new ArrayList<>();
        }
        
        public void addNode(int num) {
            if (arr == null) arr = new ArrayList<>();
            
            arr.add(num);
        }
    }
}

 

테스트 1 〉	통과 (0.51ms, 77.5MB)
테스트 2 〉	통과 (0.81ms, 78.1MB)
테스트 3 〉	통과 (0.63ms, 81.4MB)
테스트 4 〉	통과 (1.31ms, 75.1MB)
테스트 5 〉	통과 (3.85ms, 76.4MB)
테스트 6 〉	통과 (4.07ms, 78.1MB)
테스트 7 〉	통과 (39.22ms, 104MB)
테스트 8 〉	통과 (38.44ms, 111MB)
테스트 9 〉	통과 (36.97ms, 112MB)

 

 

 

 

 

너비 우선 탐색(BFS)로 탐색했다.

우선 노드 번호와 해당 노드가 연결되어 있는 노드 번호들을 묶기 위해서 Node라는 객체를 정의하였고, 거리는 far로 수정하였다.

그래서 만약에 현재 가장 멀다고 적어놓은 position의 값보다 far이 더 넓다면 해당 far로 answer과 position을 리셋했고, 같다면 answer++를 하였다.

그래프에 대해서 어려운데 이번에는 비교적 잘 푼 것 같다.

 

 

 

 

그래프 설명 참고

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?