[알고리즘 PS] 백준 5567번 결혼식 자바 문제풀이

[알고리즘 PS] 백준 5567번 결혼식 자바 문제풀이

728x90

문제

해당 포스팅은 백준의 5567번 결혼식 의 접근과 해결 방법을 설명한 글 입니다.

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이 문제는 시작 노드부터 얼마나 떨어져 있는지를 확인하고 떨어진 거리가 2 이상 3 이하면 count 를 증가시키면 되는 문제이다.

해결법

시작 노드부터 다른 모든 노드까지의 거리를 찾기 위해 BFS 를 이용할 수 있따.

정답 코드

public class Main { public static void main(String[] args) throws 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()); List> graph = new ArrayList<>(); for (int i = 0; i <= n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { String[] s = br.readLine().split(" "); int from = Integer.parseInt(s[0]); int to = Integer.parseInt(s[1]); graph.get(from).add(to); graph.get(to).add(from); } int[] depth = new int[n + 1]; Queue queue = new LinkedList<>(); queue.add(1); depth[1] = 1; while(!queue.isEmpty()) { int front = queue.remove(); for(int value : graph.get(front)) { if(depth[value] == 0) { depth[value] = depth[front] + 1; queue.add(value); } } } int count = 0; for (int i = 2; i < depth.length; i++) { if(depth[i] == 2 || depth[i] == 3) { count++; } } bw.write(String.valueOf(count)); bw.flush(); bw.close(); } }

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

728x90

from http://wonit.tistory.com/565 by ccl(S) rewrite - 2021-08-03 01:26:24