백준 5567 - 결혼식 (자바 - 그래프)

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

5567번: 결혼식

 

* 문제 요약

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

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

 

* 입력

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

 

* 출력

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

 

* 예시

 

* 해결 과정

a와 b, b와 a는 서로 쌍방으로 친구관계이므로 기본적으로 양방향 그래프임을 고려한다.

들어오는 입력을 보고 2차원 배열에서 (a, b) (b, a) 두 인덱스 쌍에 대해 1을 저장하여 서로 친구관계임을 명시해준다.

 

2차원 배열상에서 bfs 탐색을 수행하되, 중복은 배제되어야 하므로 결혼식에 초대하는 친구들에 대한 정보를 Set 자료구조에 저장해준다.

2차원 배열에서 1번째 행을 탐색하되, 행에서 1이 저장되어 있는 열은 1행과 친구관계라는 뜻이므로 우선 해당 열 번호를 Set 자료구조에 저장해주고, 이 열 번호에 해당하는 행을 탐색하여 1이 저장되어 있는 열에 대한 정보 또한 Set 자료구조에 저장해준다.

이때 1번째 열은 상근이를 뜻하므로 이 경우엔 1이 저장되어 있다고 해도 건너뛰어야 한다.

 

1번째 행에 대한 탐색이 끝난 시점의 Set 자료구조 크기가 곧 결혼식에 초대하는 친구들의 숫자가 된다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    static int[][] weddingArray;
    static Set<Integer> inviteSet = new HashSet<>();
    static int n;

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        weddingArray = new int[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            String[] input = br.readLine().split(" ");

            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

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

        for (int i = 1; i < n + 1; i++) {
            if (i != 1) {
                if (weddingArray[1][i] == 1) {
                    bfs(i);
                }
            }
        }

        bw.write(inviteSet.size() + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private void bfs(int i) {
        inviteSet.add(i);

        for (int index = 0; index < n + 1; index++) {
            if (weddingArray[i][index] == 1 && index != 1) {
                inviteSet.add(index);
            }
        }
    }
}

 

그래프로 따지자면 루트 노드에서 최대 2단계만큼 밑으로 내려갈 때 해당 범위안에서 연결되어 있는 자식 노드가 총 몇 개 있는지 구해주면 되는 문제이므로 그래프 탐색 문제에 해당된다.