[백준 5567] 결혼식 (Java) - BFS

 

https://www.acmicpc.net/problem/5567

결혼식

문제

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

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

입력

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

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

3

예제 입력 2 복사

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

예제 출력 2 복사

0

힌트

예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대한다.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 상근이 동기의 수
        int M = Integer.parseInt(br.readLine()); // 리스트 길이

        boolean[] visited = new boolean[N+1]; // 방문배열 (학번 1번부터 시작)
        ArrayList<Integer>[] graph = new ArrayList[N+1];

        // 인접리스트 초기화
        for (int i=1; i<N+1; i++){
            graph[i] = new ArrayList<>();
        }

        // 친구관계 정보입력
        StringTokenizer st;
        while (M-->0){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            // 친구관계 양방향 저장
            graph[A].add(B);
            graph[B].add(A);
        }

        Queue<int[]> queue = new LinkedList<>();
        visited[1] = true; // 상근이 본인
        queue.offer(new int[]{1,0}); // {현재번호, 깊이}

        int count = 0;

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

            if (depth >=1 && depth <=2){
                count++;
            }

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

            for (int next : graph[peer]){
                if (!visited[next]){
                    visited[next] = true;
                    queue.offer(new int[] {next, depth+1});
                }
            }
        }

        System.out.println(count);
    }
}

• BFS를 활용한 문제
• 친구관계 depth가 2까지만 탐색하여 친구관계를 count하여야 한다.
  • 상근이의 학번은 1번
  • 친구관계는 양방향
  • 초대 대상 : 1번의 친구, 그리고 친구의 친구 (총 깊이 2까지만 탐색)

문제풀이 전략

• BFS 탐색을 이용해 깊이 2까지만 탐색
• visited[] 배열로 중복초대 방지
• 친구 관계를 양방향 그래프로 저장