115591 - MooTube (Java)

📌 문제 설명

백준 15591번 - MooTube

• MooTube는 N개의 영상이 서로 연결된 그래프(트리 구조)에서, USADO(연결 강도)라는 가중치를 가지고 있다.
• 사용자가 특정 영상에서 시작하여 USADO가 k 이상인 영상의 개수를 찾는 문제.
• Q개의 질의가 주어지며, 각 질의는 (k, num) 형태이다.
  • num부터 시작하여 USADO가 k 이상인 모든 노드 개수를 출력해야 한다.

---

💡 접근 방식

🔹 그래프 탐색 방식 선택 (DFS vs BFS)

이 문제는 "최단 거리"를 구하는 것이 아니라,
"하나의 노드에서 특정 조건을 만족하는 모든 노드를 찾는 문제"이다.
따라서, BFS로 풀었지만 BFS보다 DFS가 더 적합하다!

---

📝 코드 구현

import java.io.*;
import java.util.*;

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int N, Q;
    private static List<int[]>[] connInfo;

    public static void main(String[] args) throws IOException {
        setting();
        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());
            sb.append(bfs(num, k)).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static int bfs(int num, int k) {
        int result = 0;
        boolean[] visited = new boolean[N + 1];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{num, Integer.MAX_VALUE});
        visited[num] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curNum = cur[0];
            int curMinVal = cur[1];

            for (int i = 0; i < connInfo[curNum].size(); i++) {
                int next = connInfo[curNum].get(i)[0];
                int nextMinVal = Math.min(curMinVal, connInfo[curNum].get(i)[1]);
                if (visited[next]) continue;
                q.add(new int[]{next, nextMinVal});
                visited[next] = true;
                if (nextMinVal >= k) {
                    result++;
                }
            }
        }
        return result;
    }

    private static void setting() throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        connInfo = new List[N + 1];
        for (int i = 0; i < N + 1; i++) {
            connInfo[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            connInfo[a].add(new int[]{b, v});
            connInfo[b].add(new int[]{a, v});
        }
    }
}

---

🧐 코드 분석

🔹 BFS로 구현

• 문제의 핵심은 한 노드에서 출발하여 특정 조건을 만족하는 모든 노드를 탐색하는 것.
• bfs()를 이용하여, 각 노드의 USADO 값이 k 이상인지 확인 후, 해당 노드를 카운트.

함수	역할
setting()	그래프 입력을 받아 양방향 트리 구조로 저장
bfs()	주어진 노드 num에서 시작하여 USADO가 k 이상인 노드 개수 탐색

---

🔥 DFS로 최적화 가능?

1. BFS는 큐(Queue) 연산이 추가적으로 발생하여 DFS보다 속도가 느릴 가능성이 있음.
2. 트리 구조에서는 DFS가 불필요한 탐색을 줄이고 메모리 사용량을 최적화할 수 있음.
3. DFS는 재귀(또는 스택)를 이용하여 불필요한 큐 연산 없이 탐색이 가능하므로 더 효율적.

BFS 코드에서 큐(Queue<int[]> q)를 스택(Stack<int[]> stack)으로 바꾸거나, 재귀로 구현하면 DFS로 변환 가능.

🔹 DFS 코드로 변경 (재귀 방식)

private static int dfs(int cur, int curMinVal, int k, boolean[] visited) {
    visited[cur] = true;
    int result = 0;

    for (int[] next : connInfo[cur]) {
        int nextNode = next[0];
        int nextMinVal = Math.min(curMinVal, next[1]);

        if (!visited[nextNode]) {
            if (nextMinVal >= k) {
                result++;
            }
            result += dfs(nextNode, nextMinVal, k, visited);
        }
    }
    return result;
}

✅ bfs(num, k) 대신 dfs(num, Integer.MAX_VALUE, k, new boolean[N+1])을 호출하면 DFS 방식으로 변환 완료.

---

🚀 BFS vs DFS 성능 비교

방식	시간복잡도	추가적인 연산	메모리 사용
BFS	O(N)	큐 연산 발생	높음 (큐 사용)
DFS	O(N)	재귀 호출로 진행	낮음 (스택 사용)

🚀 트리 구조에서는 DFS가 불필요한 큐 연산을 줄이고, 메모리 효율성이 높기 때문에 더 빠를 가능성이 큼.
🚀 하지만 문제 상황에 따라 BFS도 적절할 수 있음 (예: 최단 거리 탐색 필요 시).

---

🎯 결론

✅ 트리에서 특정 조건을 만족하는 모든 노드를 탐색하는 문제이므로 BFS보다 DFS가 더 적합할 가능성이 큼.
✅ 하지만 현재 코드는 BFS로 구현되어 있으며, 최적화를 위해 DFS로 변환 가능.
✅ 트리 구조에서 DFS는 불필요한 탐색을 줄이고, 큐 연산을 없애므로 성능이 개선될 수 있음.