[백준 / Java] 5567 결혼식

문제 정보

• 번호, 제목: 5567 결혼식
• 난이도: silver 2
• 태그: 그래프 이론, 그래프 탐색

• 소요 시간: 38m

풀이

DFS 또는 BFS로 풀 수 있는 문제이다. 가장 먼저 떠오른 풀이는 BFS였다.

bfs 함수 안의 로직이 중요한데,
1. Node(학번:1, depth:0)을 큐에 넣는다.
2. 큐가 empty가 될 때까지 가장 앞에 있는 것을 poll()하면서 while문을 돈다.
3. (i) 만약 방금 큐에서 나온 노드의 depth가 0이면 나 자신(상근)이므로 ans를 증가시키지 않고 인접한 노드들을 본다. (ii) 만약 방금 큐에서 나온 노드의 depth가 1이면, 상근이의 친구이므로 ans를 증가시키고 그 인접한 노드들을 본다. (iii) 만약 depth = 2이면 상근이의 친구의 친구임으로 얘네까진 결혼식에 초대한다. 하지만 얘네의 친구는 초대할 수 없다. 따라서 ans를 증가시키고 인접 노드를 보지 않도록 continue해준다.
4. 3-(i), (ii)의 경우 인접 노드를 보면서 이미 방문되었다면 뛰어넘고, 아니라면 방문처리를 해주고 큐에 넣는다.

코드는 다음과 같다.

import java.util.*;
import java.io.*;
class Main {
    static int N, M;
    static boolean visited[] = new boolean[505];
    static int ans = 0;
    static ArrayList<ArrayList<Integer>> adj;

    static class Node {
        int cur; int depth;
        Node(int cur, int depth) {
            this.cur = cur;
            this.depth = depth;
        }
    }

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());

        // 인접 리스트 초기화
        adj = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=N; ++i) {
            adj.add(new ArrayList<Integer>());
        }

        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        for(int i=0; i<M; ++i) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adj.get(a).add(b);
            adj.get(b).add(a);
        }

        bfs(1);

        bw.write(ans + "\n");
        bw.flush();
    }

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

        while(!q.isEmpty()) {
            int cur = q.peek().cur;
            int depth = q.peek().depth;
            q.remove();

            if(depth >= 2) {
                ans++; continue;
            } if(depth == 1) {
                ans++;
            }

            ArrayList<Integer> list = adj.get(cur);
            for(int next : list) {
                if(visited[next]) continue;
                visited[next] = true;
                q.add(new Node(next, depth+1));
            }
        }
    }

}

나는 처음에 이 문제는 BFS로만 풀리고, DFS는 불가능한 문제일 것이라고 생각했다. 왜냐하면 나는 평소에 depth를 볼 필요가 없는 문제를 많이 접했기 때문에 DFS를 이런 식으로 짰다.

    static void dfs(int cur, int depth) {
        visited[cur] = true; // *방문처리

        if(depth ==2) return; // depth를 볼 필요가 없는 문제에선 이런 건 없어도 됨

        ArrayList<Integer> cur_adj = adj.get(cur);
        for(int next : cur_adj) {
            if(visited[next]) continue; // *이미 방문함
            dfs(next, depth+1);
        }

주석에서 *방문처리, *이미 방문함 이 부분이 중요한데, 나는 보통 DFS 함수 가장 위에서 방문처리를, DFS를 호출하기 직전에 방문이 된 건지 확인했었다.
그러면 이런 문제가 발생한다.

원래는 dfs(학번:3, depth:1)이 호출되고, 3번이 자신의 친구인 4번을 초대해서 결혼식에는 3명이 오는 것이 맞는데, 내가 짠 코드에서는 visited 배열을 검사하여 이미 dfs(3,2)에서 방문된 3 노드를 방문하지 않게 된다. 그래서 4번이 초대되지 않게 되는 것이다.

하지만 visited 배열을 검사할 필요 없이, depth 값만 확인하여 dfs를 작성하면 dfs로도 풀 수가 있다.

    static void dfs(int cur, int depth) {
        visited[cur] = true;
        if(depth == 2) {
            return;
        }

        ArrayList<Integer> cur_adj = adj.get(cur);
        for(int next : cur_adj) {
            dfs(next, depth+1);
        }
    }

이렇게 짜면, 함수를 빠져나왔을 때, visited 배열에 결혼식에 참석하는 사람들만 true로 찍혀있게 된다.
여기서 주의할 점은 1번인 나 자신(상근)도 포함이 된다는 것이다. 따라서 2번부터 true의 개수를 세어주든지, 전체 트루의 개수에서 1을 빼주자.