[SW Expert] 5521. 상원이의 생일파티

생각

상원이의 생일 파티가 열린다! 상원의 친구와 그 친구의 친구까지 초대할 수 있다. 초대장이 총 몇 장 필요한지 출력하시오

처음 생각

친구들을 모두 초대할 수 있는 지 알아 연관된 친구들을 다 초대하기위해 DFS로 탐색을 진행하여 구현하였다.

다음 생각

DFS로 탐색을 하니 안되는 케이스가 있어서 살펴보니, 친구의 친구 까지만 초대장을 줄 수 있었고 다음과 같은 반례도 있었다.

1 2
1 3
2 3
3 4

위와 같은 Case의 경우에 DFS로 탐색시 1 - 2 - 3 으로 끝나는 반면 BFS로 탐색시에는 1 - 2 - 3 - 4 로 탐색이 되어진다.

다다음 생각

따라서 BFS로 구현을 하고 카운트 변수 cnt를 +1시키면서 진행하여 처음 값을 1로 주었으므로 1-2-3 까지 들어온 자료들은 초대장을 주어야하므로 결과값을 +1 시키고 4가되면 반복문을 빠져나오도록 하였다.

방안

1) 현재 하고있는 풀이 방향이 아닌것 같고, 다른 방안이 떠오르면 빠르게 다시 작성하는게 좋은 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Solution {
    static int n,m;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=tc;i++) {
            List<ArrayList<Integer>> list = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            for(int j=0;j<=n;j++)
                list.add(new ArrayList<>());
            
            for(int j=0;j<m;j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                list.get(a).add(b);
                list.get(b).add(a);
            }
            result = -1;
            solve(list);
            sb.append("#"+i+" "+result+"\n");
        }
        System.out.print(sb);
    }
    
    static int result;
    private static void solve(List<ArrayList<Integer>> list) {
        boolean[] visited = new boolean[n+1];
        Queue<Pair> queue = new LinkedList<>();
        visited[1] = true;
        queue.add(new Pair(1,1));
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            if(t.cnt>=4)
                break;
            result++;
            for(int i=0;i<list.get(t.n).size();i++) {
                if(visited[list.get(t.n).get(i)]) continue;
                queue.add(new Pair(list.get(t.n).get(i),t.cnt+1));
                visited[list.get(t.n).get(i)] = true;
            }
        }
    }
    
    static class Pair{
        private int n;
        private int cnt;        
        public Pair(int n,int cnt) {
            this.n = n;
            this.cnt = cnt;
        }
    }
}