(알고리즘 스터디) 14주차 수_Graph📈_(Programmers) 가장 먼 노드

🌟 프로그래머스 / Graph / Level 2 / 가장 먼 노드

📃 문제

프로그래머스

🚫 제한 사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

👀 입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

🤔 풀이 방법

예시 1의 그래프 형태

1️⃣ 그래프 구현

➡️ 그래프 구현 방법에는 크게 (1) 인접 배열 사용 과 (2) 인접 리스트 사용이 있는데 공간 효율성을 위해 둘 중 인접 리스트 사용을 선택했다. 또한 노드의 개수 n 이 미리 주어졌기 때문에 인접 리스트 구현에 있어 배열 + 리스트 조합을 사용하였다.

 

① 그래프 선언 및 초기화

// 노드를 나타내는 배열 생성
ArrayList<Integer>[] list = new ArrayList[n+1];

// 인접 노드를 담기위한 리스트 생성
for (int i=0; i<=n; i++) list[i] = new ArrayList<>();

// input edge 2차원 배열의 값을 list 로 담는 과정
for (int[] e : edge) {
    list[e[0]].add(e[1]);
    list[e[1]].add(e[0]);
}

생성된 인접 리스트의 형태

2️⃣ 인접 노드의 최단거리 탐색

➡️ 그래프 탐색의 방법에는 크게 (1) DFS 와 (2) BFS 가 있는데, "최단거리" 라는 키워드를 보자마자 BFS 로 접근해야겠다는 생각이 들었다.

 

① 그래프에서의 BFS 탐색 과정

➡️ 그래프에서 BFS 탐색 과정에 사용되는 자료구조는 (1) 큐 (Queue) 와 방문확인을 위한 (2) boolean 타입의 visited 배열 이다. 시작 노드부터 인접한 노드들을 차례대로 Queue 에 담는다. 단, 이미 visited 된 노드라면 Queue 에 담지 않고 지나간다.\

✔️ 그래프 탐색 순서
① ➡️ ③ ➡️ ② ➡️ ⑥ ➡️ ④ ➡️ ⑤

➡️ 노드 ① 로 부터 거리 1 인 ②, ③ 을 먼저 탐색 후 거리 2 인 ④, ⑤, ⑥ 을 탐색한다.

/*
목적 : 시작노드로부터 노드들의 최단 거리를 측정
변수 : start ➡️ 탐색을 시작하는 노드
*/
public static void BFS (int start) {
    int tmp = 0; // Queue 에서 poll 한 값을 담기 위한 지역 변수
    visited[start] = true; // 시작 노드를 방문 처리

    q.add(start); // Queue 에 시작 노드를 담음

    while (q.size() != 0) {
        tmp = q.poll();

        for (int node : list[tmp]) { // 인접한 노드들을 확인
            // 경우 (1) 이미 방문한 노드 : continue
            if (visited[node]) continue;
            // 경우 (2) 방문 전 노드 : 방문처리 및 Queue 에 담음
            visited[node] = true;
            q.add(node);
            // 최단 거리 : 인접 노드 거리 + 1
            len[node] = len[tmp] + 1;
        }
    }
}

최단 거리 확인 배열

② 최단거리 중 max 값 확인 및 개수 확인

➡️ 최단 거리가 담긴 변수 len 을 Arrays.sort() 를 통해 오름차순 정렬하고, 마지막 값을 max 로 정한다. 그 후 len 배열을 완탐을 통해 max 값과 일치하는 변수의 개수를 확인하면 곧 answer 가 된다.

// 최대값 확인
Arrays.sort(len);
int max = len[n];

// 개수 확인
for (int i=0; i<=n; i++) {
    if (len[i] == max) answer++;
}

3️⃣ 결과 확인

➡️ 모든 테스트 케이스에서 통과하였다.

💻 풀이 코드

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;

class Solution {
    // 그래프 생성을 위한 인접 리스트 선언
    public static ArrayList<Integer>[] list;
    // BFS 에서 방문 확인을 위한 boolean 배열 선언
    public static boolean[] visited;
    // BFS 에서 넓이 우선 탐색을 위한 Queue 선언
    public static Queue<Integer> q; 
    // 가장 멀리 떨어진 노드를 확인하기 위한 ArrayList 선언
    public static int[] len;
    
    public int solution(int n, int[][] edge) {
        // 초기화
        int answer = 0;
        visited = new boolean[n+1];
        q = new LinkedList<>();
        len = new int[n+1];
        list = new ArrayList[n+1];
        for (int i=0; i<=n; i++) list[i] = new ArrayList<>();
        
        // edge 2차원 배열의 값을 list 로 담는 과정
        for (int[] e : edge) {
            list[e[0]].add(e[1]);
            list[e[1]].add(e[0]);
        }
        
		// // 그래프 출력
		// for (int i = 1; i <= n; i++) {
		// 	for(int j = 0 ; j < list[i].size();j++)
		// 		System.out.print(list[i].get(j)+" ");
		// 	System.out.println();
		// }
        
        BFS(1);
        
        // // 깊이 확인
        // for (int d : len) {
        //     System.out.print(d + " ");
        // }
        
        // 최대값 확인
        Arrays.sort(len);
        int max = len[n];
        
        // 개수 확인
        for (int i=0; i<=n; i++) {
            if (len[i] == max) answer++;
        }
        
        return answer;
    }
    
    public static void BFS (int start) {
        int tmp = 0;
        visited[start] = true;
        
        q.add(start);
        
        while (q.size() != 0) {
            tmp = q.poll();
            
            for (int node : list[tmp]) {
                if (visited[node]) continue;
                visited[node] = true;
                q.add(node);
                len[node] = len[tmp] + 1;
            }
        }
    }
}

 

[level 3] Title: 가장 먼 노드, Time: 110.52 ms, Memory: 97.7 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@684d868