<코테 챌린지> 결혼식 (백준 5567번)

❓ 문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

📥 입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

📤 출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

📥 예제 입력

6
5
1 2
1 3
3 4
2 3
4 5

📤 예제 출력

3

 

👩🏻‍💻 내 코드

package baekjoon.코테챌린지;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 결혼식 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt(); // 동기 수
        int m = in.nextInt(); // 친구 관계 수


        // 각 노드에 연결된 친구들을 저장할 배열
        ArrayList<Integer>[] friends = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            friends[i] = new ArrayList<>();
        }

        // 친구 관계
        for (int i = 0; i < m; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            friends[a].add(b);
            friends[b].add(a);
        }

        // 초대할 친구 찾기 (BFS 이용)
        boolean[] visited = new boolean[n + 1];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});  // 상근이와 깊이 0
        visited[1] = true;

        int inviteCount = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentFriend = current[0];
            int depth = current[1];

            if (depth >= 2) continue;  // 친구의 친구까지만 탐색

            for (int friend : friends[currentFriend]) {
                if (!visited[friend]) {
                    visited[friend] = true;
                    queue.add(new int[]{friend, depth + 1});
                    inviteCount++;
                }
            }
        }

        System.out.println(inviteCount);
    }
}

 

💡 코드 접근

 

이 문제에서 상근이는 1번 학번이고, 친구 관계가 주어졌을 때 친구들과 친구의 친구까지 초대할 수 있다.

 

이 문제는 그래프 탐색을 통해 풀 수 있다.

상근이를 시작점으로 친구 관계를 탐색해가면, 친구와 친구의 친구를 쉽게 찾을 수 있다.

그래프에서 상근이와 직접적으로 연결된 노드와 그 친구의 친구 노드를 찾아내면 된다.

 

그래프 탐색 문제는 BFS 또는 DFS를 사용하여 풀 수 있는 대표적인 유형이다.

이번 문제에서는 가까운 거리부터 탐색해야 하므로 BFS가 적합하다.

 

<BFS 핵심>

• Queue를 사용하여 탐색 구현
• 중복 방문을 막기 위한 방문 여부 체크
• 주어진 문제에서 두 단계의 친구까지 탐색하는 것이 핵심이었다.>>> BFS가 해결. 즉 문제의 핵심을 파악해 어떤 방법을 선택할 건지가 중요
• BFS를 통해 상근이로부터 2단계까지만 탐색하고, 그 사람들을 초대하면 된다.

코드 설명

1. 각 동기들을 노드로, 친구 관계를 간선으로 그래프를 만든다.
2. ArrayList<Integer>[] friends 배열을 사용해 각 노드에 연결된 친구들을 저장한다.
3. 상근이의 학번인 1번 노드를 시작으로, BFS 탐색을 진행한다.상근이로부터 2단계까지만 탐색하고, 탐색된 친구들은 visited 배열로 중복 탐색을 방지한다.
4. BFS는 Queue를 사용해 탐색하고, 가까운 친구들부터 탐색하므로 친구와 친구의 친구까지 찾아낼 수 있다.

.