[BOJ] 백준 5567 결혼식-java

문제

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

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

입력

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

출력

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

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

	import java.io.*;
	import java.util.StringTokenizer;
	public class boj_5567 {
	public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	int n = Integer.parseInt(br.readLine());
	int m = Integer.parseInt(br.readLine());
	int friend1, friend2, answer = 0;
	int[][] matrix = new int[n + 1][n + 1];
	boolean[] invite = new boolean[n + 1];
	for (int i = 0; i < m; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
	friend1 = Integer.parseInt(st.nextToken());
	friend2 = Integer.parseInt(st.nextToken());
	matrix[friend1][friend2] = 1;
	matrix[friend2][friend1] = 1;
	}
	for (int i = 2; i < n + 1; i++) {
	if (matrix[1][i] == 1) {
	if (!invite[i]) {
	answer++;
	invite[i] = true;
	}
	for (int j = 2; j < n + 1; j++) {
	if (matrix[i][j] == 1 && !invite[j]) {
	answer++;
	invite[j] = true;
	}
	}
	}
	}
	System.out.print(answer);
	}
	}

view raw boj_5567.java hosted with ❤ by GitHub

풀이

문제에서  상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이며 상근이가 1번이라고 나와있습니다.

그렇기 때문에 예제 입력에서 1 2, 1 3, 3 4, 2 3, 4 5 이렇게 주어지면 상근이(1)은 2,3과 친구이므로 2,3을 초대하고 3의 친구 4까지 초대하게 되어 2,3,4 총 3명을 초대하므로 답은 3입니다.

상근이는 친구와 친구의 친구까지만 초대하면 되기때문에 딱 두 번만 확인해보면 됩니다.

먼저 상근이에서 출발합니다.

상근이의 친구(학번=i)는 matrix[1][i] = 1입니다. 

matrix[i][j] = 1이라는 것은 i와 j가 친구라는 뜻입니다.

그러므로 matrix[1][i]의 값이 1이라면 상근이의 친구이므로 초대하고 answer의 값을 1 증가시킵니다.

이미 초대했는지 안했는지를 알기 위해 invite라는 boolean array를 이용하여 i번을 초대했다면 true로 바꿔줍니다.

그리고 i번을 초대하면 i번의 친구 또한 초대하게 되므로 matrix[i][j] = 1이라면 j번을 초대합니다.

조건문에는 항상 초대하지 않은 친구라면 초대를 하고 answer의 값을 증가시켜야 하기때문에 !invite[i]를 넣어 확인을 해줍니다.

그렇게 상근이의 친구 i와 i의 친구 혹은 친구들을 초대하면 answer 값이 나옵니다.