글 읽기 - 반례 부탁드립니다.

junhui4955 4년 전 0

주어진 테스트케이스 다 맞는거 같은데 몇 % 안가서 틀리네요.

import java.util.Scanner;

public class Main {

	static int N;
	static int[] people;
	static int[][] map;
	
	static boolean[] achk;
	static boolean[] bchk;
	static int result;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		people = new int[N];
		for (int i = 0; i < N; i++) {
			people[i] = sc.nextInt();
		}
		
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			int connect = sc.nextInt();
			for (int j = 0; j < connect; j++) {
				int node = sc.nextInt() - 1;
				map[i][node] = 1;
			}
		}
		
		result = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			findMinWard(i);
		}
		
		if(result == Integer.MAX_VALUE) result = -1;
		System.out.println(result);
		
	}
	
	static void findMinWard(int start) {
		for (int i = 0; i < N; i++) {
			if(i != start) {
				achk = new boolean[N];
				achk[start] = true;
				bchk = new boolean[N];
				bchk[i] = true;
				Bdfs(i);
				if(check()) {
					int asum = 0;
					int bsum = 0;
					
					for (int j = 0; j < N; j++) {
						if(achk[j]) {
							asum += people[j];
						}else if(bchk[j]){
							bsum += people[j];
						}
					}
					result = Math.min(result, Math.abs(asum - bsum));
				}
				
				Adfs(start, i);
			}
		}
	}
	
	static void Adfs(int v, int otherLand) {
		
		for (int i = 0; i < N; i++) {
			if(map[v][i] != 0 && !achk[i] && i != otherLand) {
				achk[i] = true;
				bchk = new boolean[N];
				bchk[otherLand] = true;
				Bdfs(otherLand);
				if(check()) {
					int asum = 0;
					int bsum = 0;
					
					for (int j = 0; j < N; j++) {
						if(achk[j]) {
							asum += people[j];
						}else {
							bsum += people[j];
						}
					}
					result = Math.min(result, Math.abs(asum - bsum));
				}
				Adfs(i, otherLand);
				achk[i] = false;
			}
		}
	}
	
	static void Bdfs(int v) {
		for (int i = 0; i < N; i++) {
			if(map[v][i] != 0 && !achk[i] && !bchk[i]) {
				bchk[i] = true;
				Bdfs(i);
			}
		}
	}
	
	static boolean check() {
		for (int i = 0; i < N; i++) {
			if(achk[i] || bchk[i]) {}
			else {
				return false;
			}
		}
		return true;
	}
}

envy2 4년 전 5

8
17 42 46 81 71 8 37 12
4 2 4 5 7
5 1 3 4 5 8
2 2 4
5 1 2 3 7 8
5 1 2 6 7 8
2 5 8
4 1 4 5 8
5 2 4 5 6 7

답은 2 인데 4라고 나오시네요

kmj67130 2년 전 0

위의 반례 케이스에 대해, 나눠지는 구역은 아래와 같습니다.

1,3,4,8 -> 인원 수 156

6,5,2,7 -> 인원 수 158

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

문제

문제

출처

ICPC

반례 부탁드립니다.

junhui4955 4년 전 0

envy2 4년 전 5

kmj67130 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말