[백준] 5567 - 결혼식

[문제링크]

5567번: 결혼식

 

0. 친구의 친구까지만 찾는 문제

 

1. BFS를 딱 두번만 돌린다

• 혹은 DFS를 깊이 2에서 종료한다 (깊이 1과 2를 공유하는 node에 유의하면서)

 

2. 방문한 노드의 수 = 초대할 사람의 수이다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int M = pint(br.readLine());
		ArrayList<ArrayList<Integer>>graph = new ArrayList<>();
		
		for (int i = 0; i < N; i++)graph.add(new ArrayList<>());
		boolean[]isV = new boolean[N];
		
		for (int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = pint(st.nextToken())-1;
			int y = pint(st.nextToken())-1;
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		
		//1부터 시작해, 2번 안에 갈수있는 사람의 수 찾기
		int count=0; //몇번 건넌 친구인지 = 몇 번 돌았는지
		int friendCnt=0;
		Queue<Integer>qu = new LinkedList<Integer>();
		qu.offer(0); //초기 node = 자기 자신
		isV[0]=true;
		while(count<2) {
			int len =qu.size();
			for (int i = 0; i < len; i++) {
				int curNode = qu.poll();
				
				int graphLen = graph.get(curNode).size();
				for (int j = 0; j < graphLen; j++) {
					int nextNode = graph.get(curNode).get(j);
					if(!isV[nextNode]) {
						friendCnt++;
						isV[nextNode]=true;
						qu.offer(nextNode);
					}
				}
				
			}
			
			count++;
		}
		System.out.println(friendCnt);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면