글 읽기 - tc는 옳바르게 나오고, 특이점을 못찾았습니다. 반례 및 코드조언 부탁드립니다.

hik3562 4년 전 0

동작 원리는

이차원 array 를 생성해서 graph를 생성하고

ArrayList 를 2개 사용해서 마을을 나누고

DFS 탐색을 이용해서 전부 갈 수 있는지 확인하고

두 마을다 한 노드에서 부터 시작해서 전부 갈 수 있다면 boolean 값을 true로 바꾸었습니다.

두 마을에 대한 flag 값이 모두 true 라면 최솟값을 갱신하였습니다.

조언 부탁드립니다.

감사합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	static int city_cnt;
	static int[] city;
	static int[][] city_graph;
	static int ans = Integer.MAX_VALUE;
	static boolean[] visit; 
	static ArrayList<Integer> ag = new ArrayList<>();
	static ArrayList<Integer> ag2 = new ArrayList<>();
	
	
	static void DFS(int node) {
		visit[node] = true;
		for(int i=0; i<city_graph[node].length; i++) {
			if(city_graph[node][i] == 1 && visit[i] == false) {
				DFS(i);
			}
		}
	}
	
	static void tDFS(int node) {
		visit[node] = true;
		for(int i=0; i<city_graph[node].length; i++) {
			if(city_graph[node][i] == 1 && visit[i] == false) {
				tDFS(i);
			}
		}
	}
	
	static boolean isAllClear() {
		boolean ok = true;
		for(int i=0; i<ag.size(); i++) {
			if(visit[ag.get(i)]==false) {
				ok = false;
				return ok;
			}
		}
		return ok; 
	}
	
	static boolean tisAllClear() {
		boolean ok = true;
		for(int i=0; i<ag2.size(); i++) {
			if(visit[ag2.get(i)]==false) {
				ok = false;
				return ok;
			}
		}
		return ok; 
	}
	static void go(int nn) {
		if(nn==city_cnt) {
			if(ag.size()==0) return ;
			if(ag2.size()==0) return ;
			
			/*for(int i=0; i<ag.size(); i++)
				System.out.print(ag.get(i)+" ");
			System.out.println();
			for(int j=0; j<ag2.size(); j++)
				System.out.print(ag2.get(j)+" ");
			System.out.println();
			
			System.out.println("------------------------------");
			*/
			
			boolean first_group = false;
			for(int i=0; i<ag.size(); i++) {
				DFS(ag.get(i));
				if(isAllClear()) {
					first_group = true;
					visit = new boolean[city_cnt];
					break; 
				}
				visit = new boolean[city_cnt];
			}
			
			boolean two_group = false;
			for(int i=0; i<ag2.size(); i++) {
				tDFS(ag2.get(i));
				if(tisAllClear()) {
					two_group = true;
					visit = new boolean[city_cnt];
					break;
				}
				visit = new boolean[city_cnt];
			}
			
			if(first_group == true && two_group == true) {
			
				int f_g = 0;
				int s_g = 0;
				for(int i=0; i<ag.size(); i++) {
					f_g+=city[ag.get(i)];
				}
				
				for(int i=0; i<ag2.size(); i++) {
					s_g+=city[ag2.get(i)];
				}
				
				if(ans>Math.abs(f_g-s_g)) ans = Math.abs(f_g-s_g);
				
			}
			
			
			
			
		}else {
			ag.add(nn);
			go(nn+1);
			ag.remove(ag.size()-1);
			ag2.add(nn);
			go(nn+1);
			ag2.remove(ag2.size()-1);
		}
	}
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		city_cnt = Integer.parseInt(br.readLine());
		city = new int[city_cnt];
		city_graph = new int[city_cnt][city_cnt]; //city는 1~n 까지 
		
		
		visit = new boolean[city_cnt];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<city_cnt; i++) city[i] = Integer.parseInt(st.nextToken());
		//비용 
		
		for(int i=0; i<city_cnt; i++) {
			st = new StringTokenizer(br.readLine());
			int go = Integer.parseInt(st.nextToken());
			for(int z=0; z<go; z++) {
				int go_two = Integer.parseInt(st.nextToken());
				city_graph[i][go_two-1] = 1;
				city_graph[go_two-1][i] = 1;
			}
		}
		//그래프 생성 
		go(0);
		
		if(ans==Integer.MAX_VALUE) System.out.println(-1);
		else
			System.out.println(ans);
		
	}

}

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

문제

문제

출처

ICPC

tc는 옳바르게 나오고, 특이점을 못찾았습니다. 반례 및 코드조언 부탁드립니다.

hik3562 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말