[백준/자바] 5567번: 결혼식

문제

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

풀이

• 상근이의 N명의 친구
• 친구들에게 2번부터 N번까지 부여(상근이가 1)
• 결혼식에 초대할 사람의 수 출력
  • 친구의 친구까지만 가능

너비 우선 탐색(BFS)을 사용하는 문제
일정 깊이 이상으로 넘어가면 탐색을 종료하고 리턴해주면 됩니다.

	public static void main(String[] args) throws IOException {
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		visited = new boolean[n+1];
		
		// 친구 관계 그래프로 저장
		graph = new boolean[n+1][n+1];
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a][b] = true;
			graph[b][a] = true;
		}
		
		System.out.println(bfs(1));
	}

• 친구 관계를 입력 받으면 2차원 배열에 저장해줍니다.

왜 graph[a][b], graph[b][a]를 둘 다 true 처리하나요?

문제를 잘 보시면 1 -> 2로 이어진 관계는 1번 혼자만 친구가 아니라 1번과 2번이 서로 친구인 관계이기 때문에 양방향으로 이어줘야 합니다.

	public static int bfs(int node) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {node, 0}); // 상근이, 깊이
		visited[node] = true; // 방문처리
		
		while (!queue.isEmpty()) {
			int[] p = queue.poll();
			int person = p[0]; // 친구
			int depth = p[1]; // 깊이
			
			if (depth >= 2) break; // 친구의 친구를 초과하면 break
			
			for (int i = 1; i <= n; i++) { // 탐색할 사람의 인간 관계 탐색
				if (!visited[i] && graph[person][i]) { // 탐색한 적 없으며, 친구 관계가 존재할 경우
					queue.add(new int[] {i, depth + 1}); // 큐에 삽입, 깊이 + 1
					visited[i] = true; // 방문 처리
					cnt++; // 친구수 + 1
				}
			}
			
		}
		return cnt;
	}

• BFS를 진행할 때, 시작 노드 뿐만 아니라 깊이도 같이 넣어주어야 합니다.
• 친구의 친구까지만 탐색을 한 뒤 종료해야 하기 때문이죠
• queue에 값을 넣어줄 때(친구 관계가 늘어날 때)마다 결괏값을 증가시켜 친구수를 파악합니다.

코드

import java.util.*;
import java.io.*;

public class Main_5567 {
	static int n, m; // 동기의 수, 리스트의 길이
	static boolean[] visited; // 방문여부
	static boolean[][] graph; // 친구 관계
	static int cnt; // 초대할 친구의 수
	
	/**
	 * 탐색 시작
	 * @param 상근이
	 * @return 초대할 친구의 수
	 */
	public static int bfs(int node) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {node, 0}); // 상근이, 깊이
		visited[node] = true; // 방문처리
		
		while (!queue.isEmpty()) {
			int[] p = queue.poll();
			int person = p[0]; // 친구
			int depth = p[1]; // 깊이
			
			if (depth >= 2) break; // 친구의 친구를 초과하면 break
			
			for (int i = 1; i <= n; i++) { // 탐색할 사람의 인간 관계 탐색
				if (!visited[i] && graph[person][i]) { // 탐색한 적 없으며, 친구 관계가 존재할 경우
					queue.add(new int[] {i, depth + 1}); // 큐에 삽입, 깊이 + 1
					visited[i] = true; // 방문 처리
					cnt++; // 친구수 + 1
				}
			}
			
		}
		return cnt;
	}
	
	public static void main(String[] args) throws IOException {
		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		visited = new boolean[n+1];
		
		// 친구 관계 그래프로 저장
		graph = new boolean[n+1][n+1];
		for (int i = 0; i < m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a][b] = true;
			graph[b][a] = true;
		}
		
		System.out.println(bfs(1));
	}
}