[백준] 5567번:결혼식 (Java 자바)

문제

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

5567번: 결혼식

 

 

풀이 및 소스코드

 

문제를 보면 친구의 친구까지만 결혼식에 초대한다고 나와있다.

따라서 BFS로 돌리되, 거리가 2를 넘어가면 종료해주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;
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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int res = 0;
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());

		ArrayList<Integer>[] f = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			f[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			f[a].add(b);
			f[b].add(a);
		}

		boolean[] v = new boolean[n];

		v[0] = true;

		Queue<Integer> q = new LinkedList<Integer>();

		q.add(0);
		int cnt = 0;
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				int x = q.poll();
				for (int nowx : f[x]) {
					if (v[nowx])
						continue;
					v[nowx] = true;
					res++;
					q.add(nowx);
				}
			}
			cnt++;
			if(cnt==2) break;
            // 거리 1 : 친구
            // 거리 2 : 친구의 친구
            // 거리가 2가 되면 종료
		}

		System.out.println(res);
	}
}