백준 5567 - 결혼식

백준 5567 - 결혼식

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

★ 풀이

상근이는 1이고 친구의 친구까지만 초대해야한다. 친구 관계는 인접리스트를 통해 구현해주고 DFS나 BFS를 통해서 친구의 친구까지의 관계를 count 해주면 된다.

DFS와 BFS 둘 다 사용할 수 있다. DFS가 코드 상으로 간단할 수 있겠으나 이 문제에서는 DFS를 통해 탐색할 경우 불필요한 node까지 탐색해야 하므로(마지막에 boolean 배열을 통해 count 해서 답 구해야함).. BFS를 통해서 구해주었다.

★ 소스 코드

BFS 풀이

import java.io.*; import java.util.*; class Friend { int idx; int cnt; public Friend(int idx, int cnt) { this.idx = idx; this.cnt = cnt; } } // 좋은 코드 흡수하기! public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n,m,ans; static ArrayList adj[]; public static void main(String[] args) throws IOException { n = Integer.parseInt(br.readLine()); m = Integer.parseInt(br.readLine()); ans = 0; adj = new ArrayList[n + 1]; for(int i = 1; i<=n; i++) { adj[i] = new ArrayList<>(); } // 상근이는 1이다. // 친구의 친구까지만(cnt=2) 초대한다. BFS를 통해서 처리한다. // 친구관계는 인접리스트를 통해 처리 for(int i = 0; i q = new LinkedList<>(); q.add(new Friend(start,2)); visited[start] = true; while(!q.isEmpty()) { Friend now = q.poll(); if(now.cnt <= 0)continue; for(int next : adj[now.idx]) { if(!visited[next]) { visited[next] = true; ans++; q.add(new Friend(next,now.cnt - 1)); } } } } }

from http://sweet-smell.tistory.com/77 by ccl(A) rewrite - 2021-11-13 18:01:54