글 읽기 - 도대체 어디에서 틀리는 걸까요........!!!

ssafy5algo 3년 전 0

테케랑 질문에 올라와 있는 반례는 모두 통과됩니다ㅠㅠㅠ

제가 푼 풀이는 >

먼저 그룹1 (g1)에 넣을수 있는 모든 경우(조합)의 수를 넣고,

나머지를 그룹2(g2)에 몰아넣은 뒤,

g1과 g2가 각각 이어진 그룹인지를 유니온파인드로 확인하고,

g1도 이어져있고, g2도 이어져있다면 각 그룹내 인구의 합을 구해서 빼는 로직입니다.

채점 35~45쯤 가서 '틀렸습니다'가 뜨는데 혹시 반례 알 수 있을까요....??

도와주시면 복받으실껍니다...

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

/* 
 * 순열 조합 케이스 만들어서 queue에 전부 넣고, 
 * 해당 케이스에 따라 union-find로 같은 root인지 검사
 * 찍어본 부분은 주석처리
*/

public class Main {

	static int N,population[],graph[][],ans=Integer.MAX_VALUE,root[];
	static boolean selected[];
	static Queue<ArrayList<Integer>> totalCase = new LinkedList<ArrayList<Integer>>();
	static Scanner sc = new Scanner(System.in);
	
	private static void dataInput() {	
		N = sc.nextInt(); // 2~10
		sc.nextLine(); // 개행제거
		
		population = new int[N+1];
		selected = new boolean[N+1];
		graph = new int[N+1][N+1];
		
		StringTokenizer st = new StringTokenizer(sc.nextLine());
		for(int i=1; i<=N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
		}
		for(int j=1; j<=N; j++) {
			int tmp = sc.nextInt();
			for(int t=0; t<tmp; t++ ) {
				int related = sc.nextInt();
				graph[j][related]=1;
			}
		}
	}
	
	// nC1 nC2 nC3 ... nC(n/2)
	// totalcase에 모든 경우 저장
	private static void makeDivSectorCase() {
		for(int i=1; i<=(N/2); i++) {
			combination(0,N,i);
		}
	}
	
	private static ArrayList<Integer> combination(int start, int n, int r) {
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		if(r==0) {
			for(int i=0; i<n; i++) {
				if(selected[i]) {
					tmp.add(i+1);
				}
			}
			totalCase.add(tmp);
			return tmp;
		}else {
			for(int i=start; i<n; i++) {
				selected[i] = true;
				combination(i+1,n,r-1);
				selected[i]=false;
			}
		}
		return tmp;
	}
	
	private static int getRoot(int x) {
		if(root[x]==x) return x;
		return root[x] = getRoot(root[x]); 
	}
	
	private static void unionRoot(int a, int b) {
		a = getRoot(a);
		b = getRoot(b);
		if(a<b) {
			root[b] = a;
		} else {
			root[a] = b;
		}
	}
	
	private static boolean isLinked(ArrayList<Integer> tmp) {
		if(tmp.size()==1) {
			return true;
		}else {
			// 0 1 2
			// 1 4 6
			root = new int[N+1];
			for(int i=1; i<=N; i++) {
				root[i]=i;
			}
			for(int start : tmp) {
				for(int end : tmp) {
					if(graph[start][end]==1) {
						unionRoot(start,end);
					}
				}
			}
//			System.out.println(Arrays.toString(root));
			int ori = root[tmp.get(0)];
			for(int i=2; i<=N; i++) {
				if( tmp.contains(root[i]) && root[i]!=ori) {
					return false;
				}
			}
			return true;
		}
	}
	 
	private static int getSum(ArrayList<Integer> tmp) {
		int sum=0;
		for(int a : tmp) {
			sum += population[a];
		}
		return sum;
	}
	
	public static void main(String[] args) {
		dataInput();
		makeDivSectorCase();
		
		while(!totalCase.isEmpty()) {
			 ArrayList<Integer> g1 = totalCase.poll();
//			 System.out.println("g1 : " + g1.toString());
			 ArrayList<Integer> g2 = new ArrayList<Integer>();
			 for(int i=1; i<=N; i++) {
				 if(!g1.contains(i)) {
					 g2.add(i);
				 }
			 }
//			 System.out.println("g2 : " + g2.toString());
//			 System.out.println("g1 연결여부 " + isLinked(g1));
//			 System.out.println("g2 연결여부 " + isLinked(g2));
			 
			 if(isLinked(g1)&&isLinked(g2)) {
				 if(ans > Math.abs(getSum(g1)-getSum(g2))) {
					 ans = Math.abs(getSum(g1)-getSum(g2));
//					 System.out.println(ans);
				 }
			 }
//			 System.out.println();
		}
		if(ans<Integer.MAX_VALUE) {
			System.out.println(ans);
		}else {
			System.out.println(-1);
		}
		
	}
    
}

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

문제

문제

출처

ICPC

도대체 어디에서 틀리는 걸까요........!!!

ssafy5algo 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말