[BOJ] 백준 5567 결혼식

https://www.acmicpc.net/problem/5567

5567번: 결혼식

 

---

 

풀이 과정

1. 상근이의 친구와 친구의 친구까지만 초대가 가능하므로 깊이가 2가 되면 리턴하는 방식의 dfs를 사용했다.
2. 양방향 리스트를 만들고, 방문한 정점을 체크할 boolean형 배열을 만든다.
3. dfs를 돌리는데 반복문을 사용해서 리스트의 해당되는 정점을 찾아 연결된 정점에 방문했다는 표시를 하고 재귀 함수를 사용한다.
4. 깊이가 2가 됐을 때, 리턴을 하고 방문된 인덱스를 찾아서 값을 센다.
5. 시작점인 정점 1을 제외하기 위해 셌던 값에서 1을 빼고 출력을 한다.

다음은 Java로 작성한 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class B5567 {
    private static ArrayList<ArrayList<Integer>> list;
    private static boolean [] checked;

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

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

        list = new ArrayList<>();
        checked = new boolean[n+1];

        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        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.get(a).add(b);
            list.get(b).add(a);
        }

        dfs(1, 0);

        int count = 0;

        for (int i = 0; i <= n; i++) {
            if (checked[i]) count++;
        }

        System.out.println(count-1);
    }

    private static void dfs(int index, int depth) {
        if (depth == 2) {
            return;
        }

        for (Integer i: list.get(index)) {
            checked[i] = true;
            dfs(i, depth + 1);
        }
    }
}