글 읽기 - 게시판 반례는 모두 통과했고 어느 부분이 틀렸는지 모르겠습니다 자바

soonil0119 2년 전 0

유니온 파인드를 이용했고, 진실을 아는 자에 대해서 먼저 유니온을 다 시키고 첫 번째 사람을 기억해놨다가

나중에 체크하는 부분에서 첫 번째 사람의 루트와 비교하는 식으로 문제를 해결했는데 어느 부분이 잘못됐을까요

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M, T, ans;
	static int[] map;
	static Queue<String> q = new LinkedList<>(); 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N+1];
		for (int i = 1; i <= N; i++) { // 유니온 파인드를 위해 자기 자신을 가리키도록 저장
			map[i] = i;
		}
		st = new StringTokenizer(br.readLine());
		T = Integer.parseInt(st.nextToken());
		if(T == 0) { // 진실을 아는자가 없으면 그냥 파티수 출력해주고 끝
			System.out.println(M);
			System.exit(0);
		}
		int start = Integer.parseInt(st.nextToken()); //첫번째로 진실을 아는자와 나머지 진실을 아는자를 union 시켜준다.
		for (int i = 1; i <T; i++) { // 진실을 아는자는 모두 연결된 상태
			union(start, Integer.parseInt(st.nextToken()));
		}
		
		for (int i = 0; i < M; i++) {
			String str = br.readLine();
			st = new StringTokenizer(str);
			q.offer(str); // 먼저 한번 파티에 해당하는 사람들을 다 연결해주고 다시 체크를해야해서 큐에 저장
			int n = Integer.parseInt(st.nextToken()); // n이 1보다 커야 두명이상이라 유니온 파인드 가능
			if(n > 1) {
				int s = Integer.parseInt(st.nextToken());
				for (int j = 1; j < n; j++) {
					union(s,Integer.parseInt(st.nextToken())); // 처음 사람과 나머지애들 모두 유니온 시킨다.
				}
			}
		}
		for (int i = 0; i < M; i++) { // 여기서 이제 파티에 진실을 아는사람이 있는지 체크한다.
			String str = q.poll();
			st = new StringTokenizer(str);
			int n = Integer.parseInt(st.nextToken());
			boolean check = false; // 해당파티에 진실을 아는사람 존재하는지 체크하는 부분
			for (int j = 0; j < n; j++) {
				if(find(map[Integer.parseInt(st.nextToken())]) == map[start]) {// 해당 사람이 진실을 아는사람과 연결되어있는지 파악
					check = true;
					break;
				}
			}
			if(!check) // 위에서 걸러진게 없으면 해당파티는 진실을 아는사람이 없다
				ans++;
		}
		System.out.println(ans);
	}
	
	static int find(int a) {
		if(map[a] == a)
			return a;
		return map[a] = find(map[a]);
	}
	
	static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a < b)
			map[b] = a;
		else 
			map[a] = b;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

게시판 반례는 모두 통과했고 어느 부분이 틀렸는지 모르겠습니다 자바

soonil0119 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말