[그래프] 백준 5567: 결혼식

문제는 간단하게 기준이 되는 1번의 친구들, 그 친구들의 친구들까지 초대(목록에 추가)한다는 내용이다.

 

BFS를 사용해서 구현했다.

 

트리 구조를 활용해 기준이 되는 1번을 level 0으로 잡고, 1번의 친구들을 level 1, 1번의 친구들의 친구들을 level 2로 잡고

 

level 2까지의 사람들만 count해서 결과를 출력하는 방향으로 구현했으며

 

level은 따로 배열을 생성해서 정해줬다.

 

소스 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, HashSet<Integer>> list = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        for(int i=0; i<M; i++){
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line, " ");
            
            int source = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());
            
            if(list.containsKey(source)){
                list.get(source).add(target);
            } else {
                HashSet<Integer> set = new HashSet<>();
                set.add(target);
                list.put(source, set);
            }
            if(list.containsKey(target)){
                list.get(target).add(source);
            } else {
                HashSet<Integer> set = new HashSet<>();
                set.add(source);
                list.put(target, set);
            }
        }
        
        Queue<Integer> qu = new LinkedList<Integer>();
        qu.add(1);
        int[] visited = new int[N+1];
        int result = 0;
        int[] level = new int[N+1];
        level[1] = 0;
        visited[1] = 1;
        
        while(!qu.isEmpty()){
            int tgt = qu.poll();
            
            if(list.containsKey(tgt) && level[tgt]<2){
                HashSet<Integer> set = list.get(tgt);
                for(int num : set){
                    if(visited[num]!=1){
                        qu.add(num);
                        visited[num] = 1;
                        result++;
                        level[num] = level[tgt]+1;
                    }
                }
                
            }
        }
        
        System.out.println(result);
    }
}
 

문제를 푸는 데 걸린 시간은 16분 정도가 걸렸다.

 

문제 풀이 결과