[프로그래머스/Level3] 가장 먼 노드 (JAVA)

📖 문제

프로그래머스

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 노드 간 연결 정보 저장하는 ArrayList 배열 ➜ List<Integer>[] A
- 1과의 거리 저장하는 배열 ➜ int[] dist
- 해당 노드 방문했는지 확인용 방문 배열 ➜ boolean[] visited

 

 

1. 인접 리스트에 두 노드 간 연결 정보를 양방향으로 저장한다.

2. 1번부터 bfs를 통해 1번 노드로부터 떨어진 거리를 계산한다.

  - 해당 노드의 정점 中 방문하지 않은 다음 정점을 방문하려고 할 때, 방문 표시와 큐에 다음 정점을 추가하는 것뿐만 아니라, 거리 값도 갱신해 거리 배열에 저장한다.

dist[next] = dist[now] + 1;

 

3. 여태 구한 거리 값 중 가장 큰 값을 구하고, 이 값이 몇 개인지 세어 정답으로 출력한다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int n;
    static int[][] edge;
    
    static List<Integer>[] A; // 인접 리스트
    static int[] dist; // 1번 노드로부터의 거리 저장용 배열
    
    static int answer = 0;
    
    public int solution(int n, int[][] edge) {
        this.n = n;
        this.edge = edge;
        
        A = new ArrayList[n+1];
        for(int i = 1 ; i <= n ; i++) {
            A[i] = new ArrayList<>();
        }
        
        for(int i = 0 ; i < edge.length ; i++) { // 양방향
            A[edge[i][0]].add(edge[i][1]);
            A[edge[i][1]].add(edge[i][0]);
        }
        
        dist = new int[n+1];
        bfs(1);
        
        return answer;
    }
    
    private static void bfs(int num) {
        int max = 0;
        
        Queue<Integer> q = new ArrayDeque<>();
        q.add(num);
        
        boolean[] visited = new boolean[n+1];
        visited[num] = true;
        
        while(!q.isEmpty()) {
            int now = q.poll();
            
            for(int next : A[now]) {
                if(!visited[next]) {
                    visited[next] = true;
                    dist[next] = dist[now] + 1; // 🔔 거리 갱신
                    q.add(next);
                    max = Math.max(max, dist[next]);
                }                
            }            
        }
        
        for(int i : dist) {
            if(i == max)
                answer++;
        }
    }
}

 

 

➕ 다른 풀이 방식

인접 리스트 활용한 방식

[프로그래머스] 가장 먼 노드-JAVA

 

---

💦 어려웠던 점

15분 소요..

 

 

 

1회독	2회독	3회독	4회독	5회독
V