[JAVA]백준_5567_결혼식

문제링크

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

5567번: 결혼식

 

이 부분을 간과해서 틀렸었다.

a1,b1만 친구관계로 연결해놓고

b1,a1는 친구관계로 연결 해주지 않았기때문이다.

 

3

2

2 1 

3 1

 

output : 2

나와야 한당

 

package BOJ;

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

public class Main_5567 {
    static int N,M;
    static boolean friend[];
    static ArrayList<Integer> list[];
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        friend = new boolean[N+1];
        list = new ArrayList[N+1];
        for(int i=0;i<=N;i++) list[i] = new ArrayList<>();

        M = Integer.parseInt(br.readLine());

        for(int m=0;m<M;m++){
            String str[] = br.readLine().split(" ");
            int start = Integer.parseInt(str[0]);
            int end = Integer.parseInt(str[1]);

            list[start].add(end);
            list[end].add(start);
        }
        dfs(1,1);

        for(int i=2;i<=N;i++){
            if(friend[i]) result++;
        }

        System.out.println(result);
    }

    static void dfs(int v,int cnt){
        if(cnt == 3) return;

        Iterator<Integer> it = list[v].iterator();
        //friend[v] = true;

        while(it.hasNext()){
            //친구 & 친구의 친구
            int num = it.next();
            friend[num] = true;
            dfs(num,cnt+1);
        }
    }
}

 

친구의 친구까지만 결혼식에 초대하기 위해 cnt를 주어서 cnt == 3이면 친구으 ㅣ친구의 친구에서 끊어주도록 했다!