[백준] 5567 결혼식

www.acmicpc.net/problem/5567

5567번: 결혼식

2020-12-06

---

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
 
public class Main5567 {
    public static int N, M, answer;
    public static List<List<Integer>> list;
    public static Queue<Integer> q;
    public static boolean vtd[];
    
    public static void solve() {
        int time = 0;
        loop:while(!q.isEmpty()) {
            int size = q.size();
            while(size > 0) {
                int x = q.poll();
                
                for(int i : list.get(x)) {
                    if(!vtd[i]) {
                        q.add(i);
                        vtd[i] = true;
                        answer++;
                    }
                }
                size--;
            }
            time++;
            if(time == 2) break loop;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        list = new ArrayList<>();
        q = new LinkedList<Integer>();
        vtd = new boolean[N+1];
        
        answer = 0;
        for(int i = 0; i <= N; i++) list.add(new ArrayList<>());
        
        for(int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.get(a).add(b);
            list.get(b).add(a);
        }
        
        vtd[1] = true;
        q.add(1);
        solve();
        
        System.out.println(answer);
        
    }
}
 

 

#문제풀이

1. 서로 친구인 경우 연결한다.

 

2. 상근이의 학번인 1을 기준으로 친구들을 체크하면서, 친구의 친구까지만 결혼식에 초대할 수 있으므로 depth가 2일때까지만 체크한다. 

 

#체크포인트

1. 런타임 에러

- 처음 제출하자마자 런타임 에러가 떠서 문제 입력값을 다시 체크해봤다. 동기의 수 n (2 ≤ n ≤ 500)이라는 조건이 있고 상근이의 학번이 1부터 시작하므로 arraylist가 N만큼 들어가야한다.