[programmers] 가장 먼 노드 (Java)

[가장 먼 노드]

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

프로그래머스

 

[접근 방식]

Queue 를 이용한 BFS 방식을 통해, 노드별 거리를 탐색한다.

 

 

[Java 코드]

1. 그래프 선언 및 간선 연결로 그래프 완성하기

: 인접 그래프를 통해 그래프 구현

//그래프 선언 및 초기화
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n + 1; i++) {
    graph.add(new ArrayList<>());
}

//간선 양방향 연결
for (int[] e : edge) {
    graph.get(e[0]).add(e[1]);
    graph.get(e[1]).add(e[0]);
}

 

2. 거리 저장 배열

출발지로 부터의 거리를 저장하는 배열

//거리 저장 배열
int[] distances = new int[n + 1];
Arrays.fill(distances, -1);
distances[1] = 0; //시작점 초기화

 

3. BFS 를 이용하여, 각 노드별 거리를 저장

// BFS 를 위한 큐
Queue<Integer> queue = new LinkedList<>();
queue.add(1); //시작점 추가

//BFS 탐색
while (!queue.isEmpty()) {
    int current = queue.poll();
    for (int neighbor : graph.get(current)) {
        //방문하지 않은 노드인 경우
        if (distances[neighbor] == -1) {
            distances[neighbor] = distances[current] + 1;
            queue.add(neighbor); // 방문한 노드 추가 -> 방문한 노드와 인접한 노드 탐색하려고
        }
    }
}

 

4. 거리 저장 배열을 통해, 최대 거리를 가진 노드의 개수를 갱신

int maxDistance = 0;
int count = 0;
for (int distance : distances) {
    if (distance > maxDistance) {
        maxDistance = distance;
        count = 1;
    } else if (distance == maxDistance) {
        count ++;
    }
}

return count;

 

- 전체 코드

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

class Solution {

    public int solution(int n, int[][] edge) {

        //그래프 선언 및 초기화
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        //간선 양방향 연결
        for (int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        //거리 저장 배열
        int[] distances = new int[n + 1];
        Arrays.fill(distances, -1);
        distances[1] = 0; //시작점 초기화

        // BFS 를 위한 큐
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); //시작점 추가

        //BFS 탐색
        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int neighbor : graph.get(current)) {
                //방문하지 않은 노드인 경우
                if (distances[neighbor] == -1) {
                    distances[neighbor] = distances[current] + 1;
                    queue.add(neighbor); // 방문한 노드 추가 -> 방문한 노드와 인접한 노드 탐색하려고
                }
            }
        }

        int maxDistance = 0;
        int count = 0;
        for (int distance : distances) {
            if (distance > maxDistance) {
                maxDistance = distance;
                count = 1;
            } else if (distance == maxDistance) {
                count ++;
            }
        }

        return count;
    }
}

 

 

[Rewind]

1. 어려웠던 점

- Queue 를 사용하는 것에 익숙하지 않았다.

- BFS 에 대해 자세히 알지 못하였다.

 

2. 알게된 점

- 그래프를 인접 리스트를 통해 구현하는 것에 대해 알게 되었다.

 

3. 개선 방안

- DFS, BFS 공부 하여, 정리 해야 한다.