백준 BOJ 1043 거짓말[자바]

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

1043번: 거짓말

문제 분석

• 굳이 이런 인생을 살아야 하고 싶은 지민이가
• 파티에서 거짓말을 할건데,
• 진실이 아는 사람이 한명이라도 있으면 거짓말을 못함.
• 근데 한 사람이 여러 파티에 가서, 한번은 거짓을 듣고 한번은 진실을 들으면, 거짓말이 들키므로 이것도 일관되게 해야 함.

 

입력조건

int_사람 수N int_파티 수M
int_진실을 아는 사람 수 int[]_진실을 아는 사람들 번호
M줄에 걸쳐서{
    int_파티에 오는 사람 수 int[]_파티에 오는 사람 명단
}

 

풀이과정

• 보자마자 서로소집합이라는 생각이 들었다.
• 진실을 아는 사람들을 한 그룹으로 묵고,
• 전 파티에 걸쳐서 사람들을 묶은 뒤에,
• 진실을 아는 그룹의 부모와 다른 부모인 애들만 오는 파티에 거짓말이 가능.

• 한번 입력받은 파티를 전부 순회하며 서로소 집합을 구한 뒤,
• 파티를 다시 순회하며 거짓말을 할 수 있는 집단 구하기.

 

코드 구성

• 유니온 파인드

static int findp(int x) {
    if(p[x] == x) return p[x];
    else return p[x] = findp(p[x]);
}
static void union(int x, int y) {
    p[findp(y)] = findp(x);
}

• 진실을 알고 있는 사람이 0일 때의 처리.

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

// 진실을 알고있는 사람 번호
int truth = 0;
try {
    // 한명 받아보고, 불가능하면 넘기기.
    truth = Integer.parseInt(st.nextToken());
} catch(Exception e) {
    // 진실을 알고있는 사람의 수가 0일 때의 처리.
    System.out.println(M);
    return;
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class BJ1043거짓말 {
    static int[] p;
    static int[][] party;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 사람 수
        int N = Integer.parseInt(st.nextToken());
        // 파티 수
        int M = Integer.parseInt(st.nextToken());
        // 서로소 집합 생성
        p = new int[N+1];
        for(int i = 0; i <= N; i++) p[i] = i;

        // 진실을 아는 사람 입력받기.
        st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());

        // 진실을 알고있는 사람.
        int truth = 0;
        try {
            truth = Integer.parseInt(st.nextToken());
        } catch(Exception e) {
            // 진실을 알고있는 사람의 수가 0일 때의 처리.
            System.out.println(M);
            return;
        }

        for(int i = 1; i < num; i++)
            union(truth, Integer.parseInt(st.nextToken()));

        // 파티 입력받기.
        party = new int[M][];
        for(int i = 0; i < M; i++)
            party[i] = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 입력받기 끝.

        for(int p = 0; p < M; p++) {
            // 모든 파티에 대해,
            int main = party[p][1];
            // 합치기.
            for(int i = 2; i <= party[p][0]; i++)
                union(main, party[p][i]);
        }

        // 순회하면서 거짓말 할 수 있는 파티 세기.
        int count = 0;
        truth = findp(truth);
        par : for(int p = 0; p < M; p++) {
            for(int i = 1; i <= party[p][0]; i++) {
                if(truth == findp(party[p][i]))
                    continue par;
            }
            // 여기에 도착하면, 거짓말 가능
            count++;
        }
        System.out.println(count);
    }

    static int findp(int x) {
        if(p[x] == x) return p[x];
        else return p[x] = findp(p[x]);
    }
    static void union(int x, int y) {
        p[findp(y)] = findp(x);
    }
}

이런 너랑 친구해주는 애들한테 고마워해라 지민아