[백준] 5567번 결혼식 - Java[BFS]

[백준] 5567번 결혼식 - Java[BFS]

 

문제 출처

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

5567번: 결혼식

 

---

※ 풀이

상근이의 친구의 친구들의 숫자를 세는 문제이다.

정점을 친구들의 학번, 간선을 친구 관계로 보았을 때 그래프 탐색으로 풀 수 있는 문제이다.

여기서는 BFS 로 풀었다.

 

---

※ 소스코드

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

public class Main {

    static boolean[] visited = new boolean[501];
    static int[] dist = new int[501];
    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[][] data = new int[n + 1][n + 1];

        while (m > 0) {
            m--;
            String[] split = br.readLine().split(" ");
            int a = Integer.parseInt(split[0]);
            int b = Integer.parseInt(split[1]);

            data[a][b] = 1;
            data[b][a] = 1;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        dist[1] = 0;
        visited[1] = true;
        while (!queue.isEmpty()) {
            int nowNode = queue.remove();

            if(dist[nowNode]<2) {
                int[] nextNodes = data[nowNode];
                for (int i = 0; i < nextNodes.length; i++) {
                    if (nextNodes[i] == 1 && !visited[i]) {
                        visited[i] = true;
                        dist[i] = dist[nowNode] + 1;
                        answer++;

                        queue.add(i);
                    }
                }
            }
        }

        System.out.println(answer);
    }
}

---