[Algorithm] 백준 5567번_결혼식(Java)

1. 5567번 결혼식

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

 

2. 문제

---

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

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

 

3. 입력

---

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

 

4. 출력

---

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

 

5. 접근 방법 및 풀이

---

1. 사람들의 관계를 양방향 인접리스트로 구현한다.
2. 상근이 친구와 그 친구의 친구까지만 초대할 수 있기 때문에 cnt로 체크를 해야한다. (cnt = 0 : 상근이의 친구들, cnt = 1: 그 친구의 친구들 , cnt = 2 : 그 친구의 친구의 친구들)
3. 방문가능한 노드는 방문 체크해주고, dfs 돌린 후 방문체크 배열에서 방문한 노드 개수 세주기

5.0.1. 예제 1을 인접리스트로 구현하면 다음과 같다.

• 1 -> 2 -> 3
• 2 -> 1 -> 3
• 3 -> 1 -> 4 -> 3
• 4 -> 5
• 5 -> 4
• 6

 

6. 코드

---

      

      

      

    
    

      <code />
    
 import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.ArrayList;
 import java.util.StringTokenizer;
 ​
 ​
 public class Main {
     static int N, M;
     static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
     static boolean[] visited;
 ​
     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());
         for (int i = 0; i <= N; i++) graph.add(new ArrayList<>());
         visited = new boolean[N + 1]; //방문체크 배열
         visited[1] = true;
 ​
         StringTokenizer st;
         for (int i = 0; i < M; i++) { // 양방향 인접리스트 구현
             st = new StringTokenizer(br.readLine());
             int from = Integer.parseInt(st.nextToken());
             int to = Integer.parseInt(st.nextToken());
             graph.get(from).add(to);
             graph.get(to).add(from);
         }
         dfs(1, 0);
 ​
         /**방문 가능한 노드 세주기*/
         int answer = 0;
         for (int i = 2; i < visited.length; i++) {// i = 1 : 상근이라 카운트X
             if(visited[i]) answer++;
         }
         System.out.println(answer);
     }
     private static void dfs(int point, int cnt){
         if(cnt == 2) { // 친구의 친구의 친구까지
             return;
         }
         for(int i : graph.get(point)) {
             visited[i] = true;
             dfs(i, cnt+1);
         }
     }
 ​
 ​
 }