[백준] 5567번 : 결혼식

5567번: 결혼식

---

[BFS]

이 문제를 depth가 2 이하인 곳만 탐색하는 DFS로 풀어보려 했으나 

6

5

1 2

1 3

3 4

2 3

4 5

의 예제 입력에서, 3 -> 4를 도달하지 못한다. 1->2 그리고 2->3을 방문하기 때문에 1 -> 3, 3 -> 4를 가지 못하는 것이다. 이미 3 정점을 방문했기 때문이다.

 

그래서 한 층씩 탐색하는 BFS가 가장 적합한 방법이라고 생각된다.

# Code </>

public class Main {

    static class Element{
        int v, floor;
        public Element(int vv, int f){
            v=vv; floor = f;
        }
    }
    static List<Integer>[] list = new ArrayList[501];
    static boolean[] visit = new boolean[501];
    static int cnt = 0;

    static void BFS(int v){

        Queue<Element> Q = new LinkedList<>();
        visit[v] = true;
        Q.add(new Element(v, 0));

        while(!Q.isEmpty()){
            Element e = Q.poll();
            int current = e.v;
            int floor = e.floor;

            for(int next : list[current])
                if(!visit[next] && floor + 1 <= 2){
                
                    cnt++;
                    visit[next] = true;
                    
                    Q.add(new Element(next, floor + 1));
                }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++) list[i] = new ArrayList<>();

        for(int i=1; i<=m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            list[h].add(t);
            list[t].add(h);
        }

        BFS(1);
        System.out.println(cnt);
    }
}