[백준OJ] 5567번 결혼식

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

5567번: 결혼식

---

 

풀이

친구와 친구의 친구까지 초대를 한다고 했으므로, 그래프를 생각했다.

 

먼저 친구관계를 그래프로 나타내준 뒤, 1번부터 bfs를 이용하여 depth가 2인 친구들까지의 수를 세어주면된다. 이때 상근이의 depth는 0으로 설정을 해준다. 아래의 코드는 상근이 자신을 포함하므로, -1을 해준 결과를 출력해주면된다.

 

시간복잡도

O(N+M)

코드

import java.util.*;

class Node{
    int sNum;
    int depth;
    public Node(int sNum,int depth){
        this.sNum=sNum;
        this.depth=depth;
    }

    public int getsNum() {
        return sNum;
    }

    public void setsNum(int sNum) {
        this.sNum = sNum;
    }

    public int getDepth() {
        return depth;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }
}
public class api {
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();

        ArrayList<ArrayList<Integer>> v=new ArrayList<>();
        for(int i=0;i<=n;i++) v.add(new ArrayList<>());

        for(int i=0;i<m;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            v.get(a).add(b);
            v.get(b).add(a);
        }

        int result=0;
        Queue<Node> queue=new LinkedList<>();
        boolean[] visited=new boolean[n+1];

        queue.offer(new Node(1,0));
        visited[1]=true;
        while(!queue.isEmpty()){
            Node now=queue.poll();
            int sNum=now.getsNum();
            int depth=now.getDepth();
            if(depth>=3) continue;
            result++;
            for(int i=0;i<v.get(sNum).size();i++){
                int next=v.get(sNum).get(i);
                if(!visited[next]){
                    queue.offer(new Node(next,depth+1));
                    visited[next]=true;
                }
            }
        }
        System.out.println(result-1);
    }
}