결혼식5567

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

내친구 + 내친구의 친구 까지만 초대하기

친척문제와 비슷하다. 2촌, 3촌이 몇명인지 파악하는 그런문제였던가..?

너비탐색으로 해결하였다

시간복잡도는
나 - 친구 - 친구의 친구
까지 뻗어나가는 노드와 엣지의 개수에 따라 달라지겠다. 문제에는 이런 조건에 대해 나와 있지 않아서 시간복잡도를 구할 수 없다

import java.io.*;
import java.util.*;

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());

        ArrayList<ArrayList<Integer>> friend = new ArrayList<>();
        for(int i = 0; i < N+1; ++i)
        {
            friend.add(new ArrayList<>());
        }
        int[] visit = new int[N+1];
        for(int i = 0; i < N+1; ++i)
            Arrays.fill(visit, -1);

        String[] input;
        for(int i = 0; i < M; ++i)
        {
            input = br.readLine().split(" ");
            friend.get(Integer.parseInt(input[0])).add(Integer.parseInt(input[1]));
            friend.get(Integer.parseInt(input[1])).add(Integer.parseInt(input[0]));
        }

        bfs(1, friend, visit);
    }

    private static void bfs(int start, ArrayList<ArrayList<Integer>> friend, int[] visit)
    {
        Queue<Integer> que = new LinkedList<>();

        que.add(start);
        visit[start] = 0;
        int ans = 0;

        while(que.isEmpty() == false)
        {
            int cur = que.poll();
            ArrayList<Integer> curNode = friend.get(cur);

            for(int element:curNode)
            {
                if(visit[element] == -1 && visit[cur] < 2)
                {
                    ans++;

                    visit[element] = visit[cur]+1;
                    que.add(element);
                }
            }
        }

        System.out.println(ans);
    }
}