[알고리즘/백준] 5567번 : 결혼식(Java)

문제	5567번 : 결혼식
문제링크	https://www.acmicpc.net/problem/5567
난이도	S2
언어	Java
분류	그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

📌 최종 정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Main {
	public static void main(String args[]) throws Exception {
		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());
		
		// 친구 관계 저장용 map (양방향)
		Map<Integer, Set<Integer>> friendMap = new HashMap<>();
		for (int i = 1; i <= n; i++) {
			friendMap.put(i, new HashSet<>());
		}
		
		// 친구 관계 입력 저장
		for (int i = 0; i < m; i++) {
			String[] input = br.readLine().split(" ");
			int a = Integer.parseInt(input[0]);
			int b = Integer.parseInt(input[1]);

			// 각 인덱스 : 사람 번호, 리스트 안에는 그 사람의 친구들이 삽입
			friendMap.get(a).add(b);
			friendMap.get(b).add(a); // 양방향
		}
		
		/* friendMap = {
			  1 : [2, 3],
			  2 : [1, 4],
			  3 : [1],
			  4 : [2],
			  5 : [],
			  6 : []  (예: n = 6일 경우)
			}
		 */

		// 상근이의 친구 (1단계)
		Set<Integer> invited = new HashSet<>(friendMap.get(1)); // invited = {2, 3}

		// 상근이의 친구의 친구 (2단계)
		for (int friend : friendMap.get(1)) { // 2, 3
			for (int ff : friendMap.get(friend)) { // 2 : 1, 4 | 3 : 1
				if (ff != 1) { // 상근이 제외
					invited.add(ff);
				}
			}
		}

		// 결혼식 초대 동기 수 출력
		bw.write(invited.size() + "\n");
		br.close();
		bw.flush();
		bw.close();
	}
}

📌 구해야 하는 정답

- 상근이의 결혼식에 초대하는 동기의 수를 출력

📌 코드 설계하기

1. 입력 

- 동기 수

- 리스트 길이

 

2. 친구 관계 저장

- Map<Integer, Set<Integer>>

friendMap = {
      1 : [2, 3],
      2 : [1, 4],
      3 : [1],
      4 : [2],
      5 : [],
      6 : []  (ex: n = 6일 경우)
}

- 1단계 : 상근이 친구

- 2단계 : 상근이 친구의 친구

 

3. 출력 - 결혼식 초대 동기 수

 

일부 친구 관계에서 상근이 친구의 친구가 먼저 입력될 경우를 정확히 반영하지 못하여 다시 풀이