백준 5567번 <결혼식>

백준 알고리즘 5567번

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

5567번: 결혼식

---

5567번

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 자신의 친구의 친구를 초대하기로 했다.

상근이가 동기들의 친구 관계를 모두 조사한 리스트가 있을 때, 결혼식에 초대할 사람의 수를 구하여라.

 

입력으로 첫 줄에 상근이의 동기 수 N이 주어지고 둘째 줄에 리스트의 길이 M이 주어진다.

그다음 M개의 줄에 친구 관계가 주어진다. (이때, a b로 주어지며 이는 a와 b가 친구라는 뜻이다.)

 

---

문제 해결

BFS를 이용해 풀 수 있다.

보통의 BFS는 큐가 빌 때까지 진행하지만, 이 문제에서는 상근이의 친구와, 상근이의 친구의 친구만 구하면 되기 때문에 2번만 진행하면 된다.

처음에 큐에 상근이의 학번인 1을 넣는다. 이 상태에서 BFS를 2번 돌린다.

1번째 돌릴 때는 큐의 크기인 1만큼 값을 꺼내서 상근이의 친구를 다시 큐에 넣는다.

→ 상근이의 친구 수를 알 수 있다.

2번째 돌릴 때는 큐의 크기(상근이의 친구 수)만큼 값을 꺼내서 상근이의 친구의 친구를 다시 큐에 넣는다.

→ 상근이의 친구의 친구 수를 알 수 있다.

 

---

코드

package boj5567;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

/*
 * BFS를 2번 돌렸다.
 * 처음 시작을 1(상근이)로
 * BFS : 현재 Q의 크기만큼 값을 꺼내서 그 친구의 인접 친구 중 count되지 않은 친구를 다시 Q에 넣는다.
 * count 값에 Q의 크기를 더한다.
 * */

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // N : 상근이의 동기 수. 1은 상근이
		int M = Integer.parseInt(br.readLine()); // M : 동기들의 친구 관계의 수.
		ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(); // adjList.get(i) : i와 친구인 사람의 list
		for (int i = 0; i < N + 1; i++) {
			adjList.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < M; i++) {
			String[] inArr = br.readLine().split(" ");
			// a랑 b랑 친구
			int a = Integer.parseInt(inArr[0]);
			int b = Integer.parseInt(inArr[1]);
			adjList.get(a).add(b);
			adjList.get(b).add(a);
		}

		int count = 0; // count : 상근이의 결혼식에 초대할 동기의 수
		boolean[] visit = new boolean[N + 1]; // visit[i] : i번 동기가 count 되었는지 표시
		Queue<Integer> Q = new ArrayDeque<>(); // Q : BFS를 돌릴 때 사용할 Q

		Q.add(1);
		visit[1] = true;

		// p = 0 -> 상근이의 친구가 Q에 들어간다.
		// p = 1 -> 상근이의 친구의 친구가 Q에 들어간다.
		for (int p = 0; p < 2; p++) {
			int size = Q.size();
			for (int q = 0; q < size; q++) {
				int n = Q.poll();
				for (int i = 0; i < adjList.get(n).size(); i++) {
					int getN = adjList.get(n).get(i);
					if (visit[getN])
						continue;
					Q.add(getN);
					visit[getN] = true;
				}
			}
			count += Q.size();
		}

		System.out.println(count);
	}

}

 

시도해본 테스트케이스

/*
4
3
1 2
1 3
4 3

3
---------------
4
1
2 4

0
---------------
4
1
1 4

1
---------------
*/

---

결과

 

---