[BOJ] 1043 거짓말 - JAVA

1. 문제

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

---

2. 풀이

유니온파인드를 이용해서 파티별로 집합을 만든 다음, 진실을 아는 그룹을 체크한다.

그 다음 파티별로 진실을 아는 그룹인지 아닌지 파악해 개수를 센다.

모든 과정에서는 사람 번호보다는 그 사람의 부모 번호를 이용해야 한다. 집합의 대표 번호로 체크해야 여러 번 반복해서 확인할 필요가 없다.

 

static 변수

int[] root	사람들의 집합체크(부모번호가 저장돼있음)
ArrayList<Integer> party	파티마다 첫번째로 입력된 사람의 부모 번호 저장

 

유니온파인드

기본적인 유니온파인드 코드다. find에서 return하면서 root[x]를 갱신하는 과정이 시간을 줄이기 위해서는 꼭 필요하다.

private static int find(int x){
   if(root[x]==x) return x;
   return root[x] = find(root[x]);
}

private static void union(int a, int b){
   int ra = find(a);
   int rb = find(b);
   if(ra==rb) return;

   root[ra] = rb;
}

 

Main

N, M, 진실을 아는 사람 입력

사람 번호가 1부터 시작하기때문에 root 크기를 N+1로 한다. root[i]에 i를 저장해서 처음에는 부모가 자기자신이 될 수 있도록 한다.

진실을 아는 사람들은 arraylist에 저장한다. 진실을 아는 사람 수가 0일 수도 있기 때문에 배열보다는 리스트가 좀 더 편하다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

root = new int[N+1];
for(int i=1;i<=N;i++) root[i] = i;

st = new StringTokenizer(in.readLine());
int K = Integer.parseInt(st.nextToken());
ArrayList<Integer> know = new ArrayList<>();
for(int i=0;i<K;i++) know.add(Integer.parseInt(st.nextToken()));

 

파티에 참석한 사람끼리 집합 생성

파티에 참석한 사람 수는 CNT에 저장해두고, 맨 처음으로 입력받은 사람의 부모번호를 찾아서 first에 저장한다.

나머지를 하나씩 입력받으면서 first와 사람들을 모두 합친다.

party 리스트에 first를 더한다.

party = new ArrayList<>();
int CNT, first;
for(int i=0;i<M;i++){
   st = new StringTokenizer(in.readLine());
   CNT = Integer.parseInt(st.nextToken());
   first = find(Integer.parseInt(st.nextToken()));
   for(int c=1;c<CNT;c++) union(first, Integer.parseInt(st.nextToken()));
   party.add(first);
}

 

진실을 아는 사람이 포함된 파티 체크

N+1크기의 check배열을 만든다.

know 리스트에 있는 사람들이 속해있는 집합을 체크해야 한다.

따라서 check[진실을 아는 사람의 부모 번호]에 true를 저장한다.

boolean[] check = new boolean[N+1];
for(int k:know) check[find(k)] = true;

 

거짓말을 해도 되는 파티 수 체크 및 출력

party 리스트에 저장된 사람들을 하나씩 체크한다.

check[파티에 첫번째로 참석한 사람의 부모 번호] = true라면 이 그룹은 진실을 아는 그룹이다.

false일때만 count++한다.

 

마지막으로 count를 출력하고 끝낸다.

int count = 0;
for(int p:party){
   if(!check[find(p)]) count++;
}

System.out.println(count);

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1043_거짓말 {
   static int[] root;
   static ArrayList<Integer> party;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      root = new int[N+1];
      for(int i=1;i<=N;i++) root[i] = i;

      st = new StringTokenizer(in.readLine());
      int K = Integer.parseInt(st.nextToken());
      ArrayList<Integer> know = new ArrayList<>();
      for(int i=0;i<K;i++) know.add(Integer.parseInt(st.nextToken()));

      party = new ArrayList<>();
      int CNT, first;
      for(int i=0;i<M;i++){
         st = new StringTokenizer(in.readLine());
         CNT = Integer.parseInt(st.nextToken());
         first = find(Integer.parseInt(st.nextToken()));
         for(int c=1;c<CNT;c++) union(first, Integer.parseInt(st.nextToken()));
         party.add(first);
      }

      boolean[] check = new boolean[N+1];
      for(int k:know) check[find(k)] = true;

      int count = 0;
      for(int p:party){
         if(!check[find(p)]) count++;
      }

      System.out.println(count);
   }

   private static int find(int x){
      if(root[x]==x) return x;
      return root[x] = find(root[x]);
   }

   private static void union(int a, int b){
      int ra = find(a);
      int rb = find(b);
      if(ra==rb) return;

      root[ra] = rb;
   }
}

---

3. 결과