[백준] 5567. 결혼식

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

1. BFS로 푸는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        boolean[][] map = new boolean[n + 1][n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            map[num1][num2] = map[num2][num1] = true;
        }

        // 1번 노드(상근이)에서 BFS 시작
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(1, 0));
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;

        while (!que.isEmpty()) {
            Node now = que.poll();

            // 현재 노드까지 오는데 2만큼 걸렸다면, 더이상 이동할 수 없음
            if (now.cost == 2) {
                continue;
            }

            for (int i = 1; i <= n; i++) {
                if (map[now.end][i] && !visited[i]) {
                    que.add(new Node(i, now.cost + 1));
                    visited[i] = true;
                }
            }
        }

        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            if (visited[i]) cnt++;
        }
        System.out.println(cnt);
    }

    private static class Node {

        int end;
        int cost;

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

2. 다익스트라로 푸는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            list.get(num1).add(num2); // num1 -> num2로 갈 수 있음을 표시
            list.get(num2).add(num1); // num2 -> num1로 갈 수 있음을 표시
        }

        // 1번 노드(상근이)에서 다른 노드로의 최단 거리 구하기
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visited = new boolean[n + 1];
        Queue<Node> que = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);

        dist[1] = 0;
        que.add(new Node(1, 0));

        while (!que.isEmpty()) {
            Node now = que.poll();

            if (visited[now.end]) continue;
            visited[now.end] = true;

            for (int next : list.get(now.end)) {
                if (dist[next] > dist[now.end] + 1) {
                    dist[next] = dist[now.end] + 1;
                    que.add(new Node(next, dist[next]));
                }
            }
        }

        // 초대하는 동기 수 계산
        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            if (dist[i] <= 2) cnt++;
        }
        System.out.println(cnt);
    }

    private static class Node {
        int end;
        int cost; // 1번 노드(상근이)에서 end번 노드까지의 비용

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