Baekjoon 5567 결혼식 JAVA

5567번: 결혼식

문제

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

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

입력

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

출력

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

풀이

친구 리스트를 입력받을 때 양방향 그래프를 그려준다.

A-B가 친구이면 B-A도 친구이기 때문이다.

BFS를 이용하여 친구 그래프를 탐색한다.

친구의 친구까지만 초대하기에 depth를 2로 설정하여 2를 넘어가면 초대하지 않는다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()), m=Integer.parseInt(br.readLine()), ans=0;
		boolean [] chk = new boolean[n+1];
		LinkedList<LinkedList<Integer>>list = new LinkedList<LinkedList<Integer>>();
		for(int i=0;i<=n;i++)	// 친구 리스트 초기화
			list.add(new LinkedList<>());
		
		for(int i=0;i<m;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken()), b=Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}	// 양쪽으로 친구 관계를 설정해준다 a->b가 친구라면 b->a도 친구이기 때문
		
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {1,0});	// 1번부터 시작하고 1번은 자 자신이므로 단계를 0으로 설정
		chk[1]=true;	// 나는 따로 방문하지 않아야 함 ( 초대할 친구 목록에 포함되지 않음 )
		while(q.size()>0) {
			int [] tmp=q.poll();
			int cur = tmp[0], depth=tmp[1];	// 현재 시작하는 사람의 번호, 친구의 단계
			for(int i=0;i<list.get(cur).size();i++) {
				int adj = list.get(cur).get(i);
				if(!chk[adj] && depth<2) {	// 친구의 친구까지만 초대하기에 depth를 2로 설정하여 2를 넘어가면 초대하지 않음
					ans++;
					chk[adj]=true;	// 방문 처리
					q.add(new int[] {adj, depth+1});	// 방문하면 다음으로 검색할 사람이 됨
				}
			}
		}
		System.out.println(ans);
	}
}