[코딩테스트] SWEA 5521 상원이의 생일파티(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 5521 상원이의 생일파티입니다.

포인트

이 문제는 그래프 탐색 문제입니다.

특정 인물(상원이, 번호 1번)을 기준으로 자신의 친구와 친구의 친구까지 초대할 수 있는 사람 수를 구하는 것이 목적입니다.
즉, 깊이 2까지 탐색하는 문제로, 단순한 BFS 또는 DFS가 아니라 범위를 제한한 탐색이 핵심입니다.

소스코드

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 Q5521 {
    private static int tc, N, M;
    private static List<List<Integer>> friends;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine().trim());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            friends = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                friends.add(new ArrayList<>());
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                friends.get(a).add(b);
                friends.get(b).add(a);
            }

            int sum = 0;
            boolean[] already = new boolean[N + 1];
            already[1] = true;
            for (int num : friends.get(1)) {
                if (!already[num]) {
                    sum++;
                    already[num] = true;
                }
                for (int next : friends.get(num)) {
                    if (!already[next]) {
                        sum++;
                        already[next] = true;
                    }
                }
            }

            sb.append("#").append(t).append(" ").append(sum).append("\n");
        }
        System.out.println(sb);
    }
}
/*
2
6 5
2 3
3 4
4 5
5 6
2 5
6 5
1 2
1 3
3 4
2 3
4 5
 */

코드 설명

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    friends.get(a).add(b);
    friends.get(b).add(a);
}

• 인접 리스트 방식으로 친구 관계를 저장할 friends 리스트를 초기화합니다.
• 사람 번호는 1번부터 시작하므로 0번은 사용하지 않습니다.
• 양방향 그래프 형태로 친구 관계를 저장합니다.

for (int num : friends.get(1)) {
    if (!already[num]) {
        sum++;
        already[num] = true;
    }
    for (int next : friends.get(num)) {
        if (!already[next]) {
            sum++;
            already[next] = true;
        }
    }
}

• 상원이(1번)의 친구(num)와 친구의 친구(next)를 순회하며 초대 가능한 사람을 탐색합니다.
• 이미 초대한 사람은 already 배열로 체크하여 중복을 방지합니다.