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

문제

해당 포스팅은 백준의 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<List<Integer>> 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<Integer> 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 에서 확인 가능합니다.