백준(Java)/23년 11월
[Java] 백준 - 1043번: 거짓말
C0MPAS
2023. 11. 21. 22:06
11월 21일(화) - 자료 구조 (1043번)
1043번: 거짓말
지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게
www.acmicpc.net
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
문제점
...
public class Main {
...
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());
...
boolean[] visited = new boolean[N+1];
for(int i=1; i<=N; i++)
{
if(know_people[i] && !visited[i])
{
int root = find(i);
for(int j=1; j<=N; j++)
{
if(find(j) == root)
{
know_people[j] = true; // 수정전: know_people[i] = true;
visited[j] = true; // 수정전: visited[i] = true;
}
}
}
}
...
System.out.println(sum);
}
}1. 만약 find(j) == root 인 경우, know_people과 visited 배열에서 해당하는 경우를 true로 바꾸고자했다
-> 조건에서 j를 사용해놓고, 그 안에서는 i를 사용해서 예제4부터 예제 7까지 모두 틀린 결과가 나왔다
-> know_people[ j ] 와 visited[ j ]로 수정하면서 정답처리
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[] parent;
static int find(int x){
if(parent[x] == x)
{
return x;
}
return parent[x] = find(parent[x]);
}
static void union(int x, int y){
x = find(x);
y = find(y);
if(x != y)
{
if(x < y)
{
parent[y] = x;
}
else
{
parent[x] = y;
}
}
}
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());
st = new StringTokenizer(br.readLine());
int know_num = Integer.parseInt(st.nextToken());
boolean[] know_people;
if(know_num == 0)
{
System.out.println(M);
return;
}
parent = new int[N+1];
for(int i=1; i<=N; i++)
{
parent[i] = i;
}
know_people = new boolean[N+1];
for(int i=0; i<know_num; i++)
{
int num = Integer.parseInt(st.nextToken());
know_people[num] = true;
}
List<List<Integer>> party_list = new ArrayList<>();
for(int i=0; i<M; i++)
{
party_list.add(new ArrayList<>());
}
for(int i=0; i<M; i++)
{
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());
for(int j=0; j<num; j++)
{
party_list.get(i).add(Integer.parseInt(st.nextToken()));
if(j != 0)
{
int now_idx = party_list.get(i).get(j);
int ex_idx = party_list.get(i).get(j-1);
union(ex_idx, now_idx);
}
}
}
boolean[] visited = new boolean[N+1];
for(int i=1; i<=N; i++)
{
if(know_people[i] && !visited[i])
{
int root = find(i);
for(int j=1; j<=N; j++)
{
if(find(j) == root)
{
know_people[j] = true;
visited[j] = true;
}
}
}
}
boolean[] go_party = new boolean[M];
for(int i=0; i<M; i++)
{
go_party[i] = true;
}
for(int i=0; i<M; i++)
{
for(int j=1; j<=N; j++)
{
if(know_people[j])
{
if(party_list.get(i).contains(j))
{
go_party[i] = false;
}
}
}
}
int sum = 0;
for(int i=0; i<M; i++)
{
if(go_party[i])
{
sum++;
}
}
System.out.println(sum);
}
}ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ