[백준/Java] 17842 : 버스 노선

📌 문제 정보

• 번호: 17842
• 제목: 버스 노선
• 난이도: Gold 2
• 분류: 트리, 그래프 이론, 수학

---

💡 접근 방식

트리에서 리프 노드(차수가 1인 정점)의 개수를 세고,
이를 이용해 필요한 최소 개수를 계산하는 문제입니다.

트리의 끝점인 리프 노드들끼리 짝을 지어 연결한다고 생각하면,

• 리프가 1개면 1
• 리프가 2개면 1
• 리프가 3개면 2
• 리프가 4개면 2

(리프 개수 + 1) / 2

---

🔹 1단계 – 트리 입력 받기

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

---

🔹 2단계 – 리프 노드 개수 세기

int cnt = 0;
for (int i = 0; i < N; i++) {
    if (graph[i].size() == 1) {
        cnt++;
    }
}

---

🔹 3단계 – 정답 계산

(cnt + 1) / 2

---

💻 핵심 코드

int cnt = 0;

for (int i = 0; i < N; i++) {
    if (graph[i].size() == 1) {
        cnt++;
    }
}

System.out.println((cnt + 1) / 2);

---

⏳ 복잡도 분석

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

---

📄 전체 코드

package B17842;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static List<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }
        StringTokenizer st;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph[from].add(to);
            graph[to].add(from);
        }

        int cnt = 0;

        for (int i = 0; i < N; i++) {
            if (graph[i].size() == 1) {
                cnt++;
            }
        }

        System.out.println((cnt + 1) / 2);
    }
}