백준 1043 거짓말 Java [DFS]

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

1043번: 거짓말

 

문제를 읽고 수도코드를 작성해봤다

 

1 ~ M까지 방문체크만들고 stack에 넣기
2번째줄 방문 체크함
1 ~ M까지 arraylist<hashset<integer>>으로 만들고
3번째줄부터 2번째 숫자부터 리스트에 담아서 저장해두기
리스트요소 해시셋에 넣기
스택 빼면서 방문체크하고 자식 스택넣기 반복

리스트 돌면서 리스트 전부다 방문체크 안했으면 카운트--

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.HashSet;
import java.util.stream.Collectors;


public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        int cnt = M;
        
        str = br.readLine().split(" ");
        int K = Integer.parseInt(str[0]);

        boolean[] truth = new boolean[N+1]; // 방문체크
        Stack<Integer> stack = new Stack<>();

        ArrayList<int[]> parties = new ArrayList<>();
        ArrayList<HashSet<Integer>> arrayList = new ArrayList<>(); // dfs 돌릴 배열들
        for (int n = 0; n <= N; n++) arrayList.add(new HashSet<>(Arrays.asList()));

        for (int i = 1; i <= K; i++) {
            int x = Integer.parseInt(str[i]);
            truth[x] = true;
            stack.add(x);
        }
        for (int j = 0; j < M; j++) {
            int[] arr = Arrays.stream(br.readLine().substring(2).split(" ")).filter(e -> e.length() > 0).mapToInt(Integer::parseInt).toArray();
            parties.add(arr);
            for (int a : arr) {
                arrayList.get(a).addAll(Arrays.stream(arr).boxed().collect(Collectors.toSet()));
            }
        }

        while (!stack.isEmpty()) {
            int s = stack.pop();
            for(int a : arrayList.get(s)) {
                if (!truth[a]) {
                    truth[a] = true;
                    stack.add(a);
                }
            }
        }

        for(int[] party : parties) {
            cnt -= check(party, truth);
        }
        System.out.println(cnt);
    }

    static int check(int[] arr, boolean[] truth) {
        for (int a : arr) {
            if (truth[a]) return 1;
        }
        return 0;
    }
}

 

예제에는 없지만 테스트케이스에 숫자들 사이에 공백이 2개인 경우가 존재한다

거르지 않으면 NumberFormat 런타임에러를 만나니까

공백을 2개짜리를 1개로 바꾸기위해 replaceAll("  ", " ")을 사용하거나 filter를 사용하면 된다!

아니면 StringTokenizer를 사용해서 숫자를 한개씩 받으면 된다!