[백준] 5567 - 결혼식

[백준] 5567 - 결혼식

[문제링크]

0. 친구의 친구까지만 찾는 문제

1. BFS를 딱 두번만 돌린다

혹은 DFS를 깊이 2에서 종료한다 (깊이 1과 2를 공유하는 node에 유의하면서)

2. 방문한 노드의 수 = 초대할 사람의 수이다

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main{ public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = pint(br.readLine()); int M = pint(br.readLine()); ArrayList>graph = new ArrayList<>(); for (int i = 0; i < N; i++)graph.add(new ArrayList<>()); boolean[]isV = new boolean[N]; for (int i = 0; i < M; i++) { StringTokenizer st = new StringTokenizer(br.readLine(), " "); int x = pint(st.nextToken())-1; int y = pint(st.nextToken())-1; graph.get(x).add(y); graph.get(y).add(x); } //1부터 시작해, 2번 안에 갈수있는 사람의 수 찾기 int count=0; //몇번 건넌 친구인지 = 몇 번 돌았는지 int friendCnt=0; Queuequ = new LinkedList(); qu.offer(0); //초기 node = 자기 자신 isV[0]=true; while(count<2) { int len =qu.size(); for (int i = 0; i < len; i++) { int curNode = qu.poll(); int graphLen = graph.get(curNode).size(); for (int j = 0; j < graphLen; j++) { int nextNode = graph.get(curNode).get(j); if(!isV[nextNode]) { friendCnt++; isV[nextNode]=true; qu.offer(nextNode); } } } count++; } System.out.println(friendCnt); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/115 by ccl(S) rewrite - 2021-08-08 23:59:56