알고리즘/99Club

99클럽 코테 스터디 24일차 TIL + 가장 먼 노드 (BFS, 최단경로)

dami97 2024. 8. 14. 12:25
반응형

소개

  • 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
  • TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
  • 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

  • 프로그래머스 - 가장 먼 노드 (문제 링크)
  • BFS(너비 우선 탐색)
  • 그래프 탐색
  • 최단 경로

 

 

문제 설명

주어진 n개의 노드로 이루어진 그래프에서, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제입니다. 가장 멀리 떨어진 노드란, 1번 노드에서 출발하여 최단 경로로 도달했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

제한사항

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

입출력 예

예제 1

n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
Output: 3

예제 설명

위의 예제에서, 1번 노드에서 가장 멀리 떨어진 노드는 6번, 4번, 5번 노드이며, 이들은 모두 4개의 간선을 통해서만 도달할 수 있습니다. 따라서 가장 멀리 떨어진 노드의 개수는 3개입니다.

 

 

문제 접근

이 문제는 그래프 탐색 문제로, BFS(너비 우선 탐색)을 이용해 1번 노드로부터 모든 노드까지의 최단 거리를 계산한 뒤, 가장 멀리 있는 노드의 개수를 찾는 방식으로 접근할 수 있습니다.

  1. 그래프 초기화
    • 주어진 간선 정보를 바탕으로 그래프를 인접 리스트 형태로 초기화합니다.
  2. BFS 탐색
    • 1번 노드부터 시작하여 BFS를 이용해 각 노드까지의 최단 거리를 계산합니다.
    • 각 노드까지의 거리를 depth로 저장하고, 방문한 노드는 다시 방문하지 않도록 visited 배열을 사용합니다.
  3. 최대 거리 계산 및 결과 반환
    • BFS 탐색이 완료된 후, 최대로 멀리 떨어진 노드의 거리를 계산하고, 그 거리를 가지는 노드의 개수를 셉니다.

 

풀이 - Java 코드

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

class Solution {

    private boolean[] visited;
    private int answer, depth;
    private ArrayList<Node>[] graph;
    private ArrayList<Node> resultList;
    private Queue<Node> queue;

    public int solution(int n, int[][] edge) {
        depth = 0;
        queue = new ArrayDeque<>(n);
        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        // 그래프 초기화
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 간선 정보 추가
        for (int i = 0; i < edge.length; i++) {
            int start = edge[i][0];
            int end = edge[i][1];
            graph[start].add(new Node(end, -1));
            graph[end].add(new Node(start, -1));
        }

        // BFS 탐색 시작
        bfs();

        // 최대 거리 노드 개수 계산
        resultList.forEach(
                node -> {
                    if (node.depth == depth) {
                        answer++;
                    }
                }
        );

        return answer;
    }

    private void bfs() {
        ArrayList<Node> nodes = graph[1];
        visited[1] = true;
        resultList = new ArrayList<>();
        resultList.add(new Node(1, 0));

        // 1번 노드에서 연결된 노드들 큐에 추가
        for (Node node : nodes) {
            resultList.add(node);
            node.depth = 1;
            queue.add(node);
            visited[node.end] = true;
        }

        // BFS 진행
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (depth < node.depth) {
                depth = node.depth;
            }
            for (Node n : graph[node.end]) {
                if (!visited[n.end]) {
                    n.depth = node.depth + 1;
                    queue.add(n);
                    resultList.add(n);
                    visited[n.end] = true;
                }
            }
        }
    }
}

class Node {
    int end;
    int depth;

    public Node(int end, int depth) {
        this.end = end;
        this.depth = depth;
    }
}

 

풀이 설명

  1. 그래프 초기화
    • 주어진 간선 정보를 기반으로 각 노드에 연결된 노드들을 인접 리스트 형태로 저장합니다.
  2. BFS 탐색
    • 1번 노드에서 시작하여 연결된 모든 노드를 BFS 방식으로 탐색합니다.
    • 각 노드까지의 거리를 depth로 계산하고, 큐를 사용해 다음에 탐색할 노드를 관리합니다.
  3. 최대 거리 계산 및 결과 반환
    • BFS 탐색을 마친 후, 최대 depth를 가지는 노드의 개수를 계산하여 반환합니다.

 

 

마무리하며

  • 이번 문제를 통해 BFS를 활용한 그래프 탐색 방법을 다시 한 번 복습할 수 있었습니다.
  • 그래프에서 최대 depth를 찾는 문제에 대해, BFS로 최단 거리를 구한 뒤, 최대 depth를 가지는 노드의 개수를 계산하여 문제를 해결했습니다.