[BOJ] 5567 결혼식

결혼식

풀이

• 상근이는 자신의 친구와 친구의 친구를 초대하기로 했다.
• 친구관계를 조사한 리스트를 갖고 결혼식에 초대할 사람의 수를 구해라.
• bfs,dfs 둘다 될 것 같은데 난 bfs로 풀었다.
• 친구의 친구까지만 고려해야 하기 때문에, bfs 돌릴 때 depth를 저장해서, depth<=1 일 때 까지만 큐에 넣었다.
• 처음에 친구관계를 저장하는 list를 단방향 그래프로 구현해서 틀렸다. 양방향으로 다시 구현했더니 맞았음

코드

import java.util.*;
import java.io.*;
public class Main {
    static int N,M;
    static List[] list;
    static boolean[] visited;
    static int answer = 0;

    static class Point{
        int x;
        int cnt;
        Point(int x, int cnt){
            this.x = x;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        list = new List[N+1];
        for(int i=0;i<=N;i++){
            list[i] = new LinkedList();
        }
        visited = new boolean[N+1];
        StringTokenizer st;
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        bfs(1);
        System.out.println(answer);

    }

    private static void bfs(int start){
        visited[start] = true;
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(start,0));

        while(!queue.isEmpty()){
            Point now = queue.poll();
            int cur = now.x;
            int cnt = now.cnt;
            for(int i=0;i<list[cur].size();i++){
                int next = (int)list[cur].get(i);
                if(!visited[next] && cnt<2){
                    visited[next] = true;
                    queue.add(new Point(next,cnt+1));
                    answer++;
                }
            }
        }
    }
}