[백준] BOJ_5567 결혼식 JAVA

BOJ_5567 결혼식

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.

---

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

---

예제 입&출력

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int n, m;
    private static ArrayList<Integer>[] lists;
    private static boolean[] visit;
    private static Queue<Node> q = new LinkedList<>();

    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());
        lists = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            lists[i] = new ArrayList<>();
        }
        visit = new boolean[m + 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());

            lists[a].add(b);
            lists[b].add(a);
        }

        q.add(new Node(1, 0));
        visit[1] = true;

        int cnt = 0;

        while (!q.isEmpty()) {
            Node curNode = q.poll();
            if (curNode.cost > 2) break;

            for (Integer next : lists[curNode.idx]) {
                if (!visit[next]) {
                    visit[next] = true;
                    q.add(new Node(next, curNode.cost + 1));
                    if (curNode.cost + 1 <= 2) {
                        cnt++;
                    }
                }
            }
        }

        System.out.println(cnt);
    }

    private static class Node {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
}

---

Comment

• Queue와 ArrayList + 배열을 이용한 그래프를 생성하여 로직을 구현했다.
• 문제의 친구의 친구까지는 각 노드간 거리(cost)를 2로 제한함을 가리킨다.

---