(5567) 결혼식

문제

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

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

입력

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

출력

 

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

---

문제 풀이

해당 문제는 그래프 탐색으로 해결 할 수 있는 문제이다. 먼저 해당 문제는 현재 자신의 직접 친구와 그 친구의 친구까지만 친구로 인정이 되고 있는 문제이다. 그렇기 때문에 어디까지 탐색해야는지 기준을 잘 정해야 풀 수 있는 문제이다. 

 

아래 그래프를 보면 쉽게 이해 할 수 있을 것이다. 

현재 1의 친구는 2,3 이고 3의 친구인 4까지만 친구로 인정이 되어 총 3이라는 답을 제출 하면된다.

---

나의 답안

import java.io.*;
import java.util.*;

public class Main {

    static List<Integer> graph[];

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int e = sc.nextInt();

        graph = new ArrayList[n + 1];

        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < e; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            graph[u].add(v);
            graph[v].add(u);
        }

        List<Integer> friends = new ArrayList<>();

        for(int next : graph[1]){
            if (!friends.contains(next)) friends.add(next);

            for (int dNext : graph[next]) {
                if(dNext != 1 && !friends.contains(dNext)) friends.add(dNext);
            }
        }

        System.out.println(friends.size());
    }
}