[백준] 1043번 '거짓말' - Java

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

1043번: 거짓말

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 14360KB | 시간 136ms | 코드 길이 1733B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	private static int[] parent;
	
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] truth = new int[n];
		
		parent = new int[n];
		for(int i = 0 ; i < n ; i++) {
			parent[i] = i;
		}
		
		st = new StringTokenizer(bf.readLine());
		int k = Integer.parseInt(st.nextToken());
		for(int i = 0 ; i < k ; i++) {
			int t = Integer.parseInt(st.nextToken()) - 1;
			truth[t] = 1;
		}
		
		int[][] party = new int[m][50];
		int[] p = new int[m];
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bf.readLine());
			p[i] = Integer.parseInt(st.nextToken());
			for(int j = 0 ; j < p[i] ; j++) {
				int v = Integer.parseInt(st.nextToken()) - 1;
				party[i][j] = v;
				if(j > 0) union_root(party[i][j - 1], party[i][j]);
			}
		}
		
		int ans = m;
		for(int i = 0 ; i < n ; i++) {
			if(truth[i] == 1) {
				truth[find_root(i)] = 1;
			}
		}
		
		int a = 0;
		for(int i = 0 ; i < m ; i++) {
			a = find_root(party[i][0]);
			if(truth[a] == 1) ans --;
		}
		
		bw.write(Integer.toString(ans));
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	private static int find_root(int x) {
		if(x == parent[x]) {
			return x;
		}
		return parent[x] = find_root(parent[x]);
	}
	
	private static void union_root(int x, int y) {
		x = find_root(x);
		y = find_root(y);
		
		if(x != y) {
			parent[x] = y;
		}
	}
}

분리집합을 이용한 코드입니다. 루트노드를 이용하여 해당 노드에 진실을 아는 사람이 있는지 확인합니다.

---

 

Try1. 틀렸습니다가 뜬 코드입니다. - 코드 길이 1562B

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

public class Main {
	private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int[] truth = new int[n];
		int[][] node = new int[n][n];
		
		st = new StringTokenizer(bf.readLine());
		int k = Integer.parseInt(st.nextToken());
		for(int i = 0 ; i < k ; i++) {
			int t = Integer.parseInt(st.nextToken()) - 1;
			truth[t] = 1;
		}
		
		int[][] party = new int[m][50];
		int[] p = new int[m];
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(bf.readLine());
			p[i] = Integer.parseInt(st.nextToken());
			for(int j = 0 ; j < p[i] ; j++) {
				int v = Integer.parseInt(st.nextToken()) - 1;
				party[i][j] = v;
				for(int r = 1 ; r <= j ; r++) {
					node[party[i][r - 1]][party[i][j]] = 1;
					node[party[i][j]][party[i][r - 1]] = 1;
				}
			}
		}
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				if(node[i][j] == 1 && truth[j] == 1) {
					truth[i] = 1;
					break;
				}
			}
		}
		
		int ans = m;
		for(int i = 0 ; i < m ; i++) {
			for(int j = 0 ; j < p[i] ; j++) {
				if(truth[party[i][j]] == 1) {
					ans --;
					break;
				}
			}
		}
		
		bw.write(Integer.toString(ans));
		
		bf.close();
		bw.flush();
		bw.close();
	}
}

 

6 5
1 6
2 4 5
2 1 2
2 2 3
2 3 4
2 5 6

이 반례(질문계시판에 있음)가 생겨서 틀린 코드입니다. 다시 돌아가는 걸 못 했습니다.

---

Search 🔍

https://sohee-dev.tistory.com/75