[그래프] 백준 5567번 결혼식 자바 (Java)

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

5567번: 결혼식

문제

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

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

입력

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

출력

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

코드

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

public class No5567 {
    static ArrayList<ArrayList<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        int ans = 0;
        visited = new boolean[n + 1];
        visited[1] = true;

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            //양방향 그래프
            graph.get(start).add(end);
            graph.get(end).add(start);
        }

        bfs(1, 0);

        for (int i = 2; i < n + 1; i++) { //상근이를 제외하고 세기
            if (visited[i]) ans++;
        }
        System.out.println(ans);

        br.close();
    }

    static void bfs(int num, int depth) {
        if (depth == 2) { // 친구의 친구까지만
            return;
        }
        for (int i : graph.get(num)) {
            visited[i] = true;
            bfs(i, depth + 1);
        }
    }
}

풀이

bfs를 이용하여 푸는 문제

친구의 친구까지 초대하므로 depth가 2인곳 까지만 탐색

친구라는 관계는 양방향 이므로 양방향 그래프로 구현 해야됨

bfs를 한후, 방문한 노드를 세어서 출력하면 답이 나옴