[프로그래머스] (Java) 가장 먼 노드 (그래프) 문제풀이

 

 

📑 1. 문제설명

---

💡 2. 접근방식

자료 만들 생각에 벌써부터 피곤하다. 하하하
 
문제 풀이에 앞서, 명색이 그래프 문제인 만큼 그래프에 대해 간략히 설명하고자 한다.

2-1. 그래프의 구조

• 노드: 원(circle)으로 표시하고, 숫자로 번호를 적는다.
• 간선: 노드를 연결하는 선(segment)으로, 모든 간선이 양방향임을 보여주기 위해 화살표 없이 직선으로 그린다.

return 하고자 하는 값은  1번 노드에서 가장 멀리 떨어진 노드의 수 이다.
즉 1번 노드에서 다른 노드들로 이동하는 최단 거리를 계산해서 최단 거리가 가장 먼 노드들이 몇 개인지를 구해야 한다. 
 

2-2. 해결 방법

(1) 인접 리스트로 그래프 만들기

 List<List<Integer>> graph = new ArrayList<>();

 
예를 들어 문제에서 제시된 vertex 배열을 이용해 인접 리스트 형태로 그래프를 만든다.
 
예) graph[1] = [2, 3] → 1번 노드와 직접 연결된 노드가 2, 3

 
예) graph[2] = [1, 3, 4, 5] → 2번 노드와 직접 연결된 노드가 1, 3, 4, 5

 
예) graph[3] = [1, 2, 4, 6] → 3번 노드와 직접 연결된 노드가 1, 2, 4, 6

 
 
이걸 정리해 보면 ▼

1번 → 2번, 3번
2번 → 1번, 3번, 4번, 5번
3번 → 1번, 2번, 4번, 6번
4번 → 2번, 3번
5번 → 2번
6번 → 3번

 
그리고 이것을 ArrayList<>를 사용해서 인접 리스트 형태의 반복문으로 만들면 아래와 같다.  
 
예를 들어, graph.get(1).addAll(Arrays.asList(3, 2));는 1번 노드와 연결된 2번, 3번 노드를 그래프에 추가하는 것이다. 

이 때 첫번째 0번 인덱스는 제외한다.
왜냐하면 그래프가 1번부터 시작하기 때문이다.
양방향 연결이므로 양쪽에 값을 추가한다.

// 그래프 초기화 (0번 노드는 사용하지 않음)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
    graph.add(new ArrayList<>());
}


// 간선 정보 반복문으로 추가
for (int[] edge : vertex) {
    int a = edge[0];
    int b = edge[1];
    graph.get(a).add(b); // a번 노드와 b번 노드 연결
    graph.get(b).add(a); // b번 노드와 a번 노드 연결 (양방향)
}

 
여기까지 간선 정보가 추가된 리스트 graph의 모습이다. 

graph[0] = []
graph[1] = [3, 2]   // 1번 노드는 3번, 2번과 연결됨
graph[2] = [3, 1, 4, 5] // 2번 노드는 3번, 1번, 4번, 5번과 연결됨
graph[3] = [6, 4, 2, 1] // 3번 노드는 6번, 4번, 2번, 1번과 연결됨
graph[4] = [3, 2]   // 4번 노드는 3번, 2번과 연결됨
graph[5] = [2]      // 5번 노드는 2번과 연결됨
graph[6] = [3]      // 6번 노드는 3번과 연결됨

---

(2) BFS로 거리 계산하기

이제 BFS를 통해 1번 노드에서 모든 노드까지의 거리를 계산한다. BFS는 큐(Queue)를 사용하여 진행된다. 
 
BFS 로직

1. 먼저 시작 노드(1번 노드)를 큐에 넣는다.
2. 큐에서 노드를 하나씩 꺼내서 그 노드와 연결된 모든 노드를 탐색한다.
3. 연결된 노드가 아직 방문하지 않은 노드라면 해당 노드를 큐에 추가하고 visited 배열에 true로 표시하여 다시 방문하지 않도록 한다.
4. 노드까지의 거리를 distance 배열에 기록한다. 이렇게하면 각 노드는 처음 발견되었을 때 최단 거리로 갱신된다.
5. BFS가 끝난 후, distance 배열에서 가장 큰 값을 찾고 해당 값과 같은 거리를 가진 노드의 개수를 count해서 return

---

👉🏻 BFS(너비 우선 탐색)을 쓰는 이유 
 

BFS는 최단 거리를 찾는 데 효과적이다. BFS(Breadth-First Search)를 사용하면 1번 노드에서 모든 노드까지의 거리를 한 번의 탐색으로 계산가능하다. 

---

💡 BFS(너비 우선 탐색)

그래프를 탐색하는 방법 중 하나인데, 쉽게 말하면 '먼저 가까운 노드부터 차례로 탐색하는 방식'이다. 1번 노드부터 시작해서 주변 노드들을 차례차례 탐색한다. BFS는 큐라는 자료구조를 통해서 구현 할 수 있다. 큐는 먼저 온 것이 먼저 나오는 순서로 작동한다. 그래서 먼저 대기한 노드부터 차례대로 탐색이 처리되고 큐에서 제거된다.

그래프 구조에서 1번 노드에서부터 BFS를 시작하면 어떻게 되는 지 과정을 하나 하나 설명 해 보겠다. 
 
선언된 큐, 배열 ▼
⚡ queue: 큐에서  노드를 꺼내면서 인접한 노드를 탐색하고 큐에 추가한다.
⚡ 방문한 노드(visited): 노드를 이미 방문했는지 여부 체크 (중복 방지용)
⚡ 거리 배열(distance): 각 노드와 시작 노드(1번 노드) 간의 거리를 기록한다.
 

distance의 [0]번 인덱스에 들어가는 값은 -1입니다.
제가 자료를 만드는 데 오류가 있었습니다. 🙏🏻
초기값은 아직 미방문이므로 distance는 모두 -1로 초기화 해 줍니다.

---

초기상태
큐: [1] (1번 노드가 큐에 들어 있음)
방문한 노드: [1] (1번 노드를 방문 처리)
 
1번 노드 탐색 시작:
1번 노드를 큐에서 꺼낸다.
1번 노드와 연결된 2번, 3번 노드를 큐에 추가한다.
 
큐: [2, 3] (2번, 3번 노드가 큐에 들어 있음)
방문한 노드: [1, 2, 3] (2번, 3번 노드를 방문 처리)
 
최단거리
distance[0]: 그래프에서 0번 노드는 존재하지 않으므로 -1
distance[1]: 1번 노드에서 1번 노드까지의 거리는 0
distance[2]: 1번 노드에서 2번 노드까지의 최단 거리는 1
distance[3]: 1번 노드에서 3번 노드까지의 최단 거리는 1

---

2번 노드 탐색

큐에서 2번 노드를 꺼내서 탐색한다.
2번 노드와 연결된 1번, 3번, 4번, 5번 노드가 있지만, 1번과 3번은 이미 방문한 노드라서 4번과 5번만 큐에 넣는다.

큐: [3, 4, 5]
방문한 노드: [1, 2, 3, 4, 5]
 
최단거리
2번 노드에서 연결된 4번, 5번 노드는 1번 노드로부터 두 번째로 탐색되는 노드들이므로 거리가 2로 갱신된다.
distance[4]: 1번 노드에서 2번 노드까지의 최단 거리는 2
distance[5]: 1번 노드에서 3번 노드까지의 최단 거리는 2

---

3번 노드 탐색

큐에서 3번 노드를 꺼내서 탐색한다.
3번 노드와 연결된 1번, 2번, 4번, 6번 노드가 있는데, 1번, 2번, 4번은 이미 방문한 노드라서 6번만 큐에 넣는다.

큐: [4, 5, 6]
방문한 노드: [1, 2, 3, 4, 5, 6]
 
최단거리
결국 6번 노드는 3번 노드를 거쳐 1번 노드로부터 거리 2에 도달하게 되므로 distance[6] 값은 2이다.
distance[6]: 1번 노드에서 2번 노드까지의 최단 거리는 2

---

4번 노드 탐색

큐에서 4번 노드를 꺼내서 탐색한다.
4번 노드와 연결된 2번, 3번은 이미 방문한 노드이므로, 큐에 추가하지 않고 거리도 갱신하지 않는다.

큐: [5, 6]
방문한 노드: [1, 2, 3, 4, 5, 6]

---

5번 노드 탐색

큐에서 5번 노드를 꺼내서 탐색한다.
5번 노드와 연결된 2번은 이미 방문한 노드이므로 큐에 추가하지 않고 거리도 갱신하지 않는다.

큐: [6]
방문한 노드: [1, 2, 3, 4, 5, 6]

---

6번 노드 탐색

큐에서 6번 노드를 꺼내서 탐색한다.
6번 노드와 연결된 3번은 이미 방문한 노드이므로 큐에 추가하지 않고 거리도 갱신하지 않는다.

큐: []
방문한 노드: [1, 2, 3, 4, 5, 6]
탐색 종료

---

모든 노드를 다 탐색한 후, distance 배열에 기록된 각 노드까지의 거리를 바탕으로 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환할 수 있다. 가장 먼 거리가 2인 노드들이 3개이므로 3을 리턴한다.  

---

⭐ 3. 정답코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        // 그래프 초기화 (0번 노드는 사용하지 않음)
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 간선 정보 반복문으로 추가
        for (int[] e : edge) {
            int a = e[0];
            int b = e[1];
            graph.get(a).add(b); // a번 노드와 b번 노드 연결
            graph.get(b).add(a); // b번 노드와 a번 노드 연결 (양방향)
        }
        
        // 거리 배열과 방문 여부 배열 초기화
        int[] distance = new int[n + 1]; // 거리 배열
        boolean[] visited = new boolean[n + 1]; // 방문 여부 배열
        visited[1] = true; // 1번 노드는 시작 노드로 방문 처리
        
        // BFS를 위한 큐 생성 (q로 변수명 변경)
        Queue<Integer> q = new LinkedList<>();
        q.add(1); // 시작 노드 1번을 큐에 추가
        
        // BFS 탐색
        while (!q.isEmpty()) {
            int nowNode = q.poll(); // 현재 노드 꺼내기
            List<Integer> nodeList = graph.get(nowNode); // 현재 노드와 연결된 노드들
            
            // 연결된 노드들 탐색
            for (int nextNode : nodeList) {
                if (!visited[nextNode]) { // 방문하지 않은 노드일 경우
                    q.add(nextNode); // 큐에 추가
                    visited[nextNode] = true; // 방문 처리
                    distance[nextNode] = distance[nowNode] + 1; // 거리 갱신
                }
            }
        }
        
        // 가장 먼 거리값 찾기
        int maxDistance = Arrays.stream(distance).max().getAsInt();
        
        // 가장 먼 거리의 노드 개수 세기
        for (int dist : distance) {
            if (dist == maxDistance) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

👏🏻 좋아요 가장 많이 받은 코드

import java.util.ArrayList;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] path = new ArrayList[n];
        ArrayList<Integer> bfs = new ArrayList<Integer>();
        int answer = 0;
        int[] dist = new int[n];
        dist[0] = 1;
        int max = 0;

        for(int i = 0; i < edge.length; i++) {
            int num1 = edge[i][0] - 1;
            int num2 = edge[i][1] - 1;
            if(path[num1] == null)
                path[num1] = new ArrayList<Integer>();
            if(path[num2] == null)
                path[num2] = new ArrayList<Integer>();
            path[num1].add(num2);
            path[num2].add(num1);
        }

        bfs.add(0);
        while(!bfs.isEmpty()) {
            int idx = bfs.get(0);
            bfs.remove(0);
            while(!path[idx].isEmpty()) {
                int num = path[idx].get(0);
                path[idx].remove(0);
                bfs.add(num);
                if(dist[num] == 0) {
                    dist[num] = dist[idx] + 1;
                    max = dist[num];
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(dist[i] == max)
                answer++;
        }

        return answer;
    }
}

---

🐦 4. 같은 유형 문제 (그래프)

[프로그래머스] (Java) 순위 (그래프) 문제풀이