글 읽기 - 시간초과(Java코드포함)

fastz 4년 전 0

TC는 모두 맞게 나오는데 완전탐색이 문제인것인지 시간초과로 통과하지 못하고있네요.

도움 부탁드립니다!

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


public class Main {

	public static class chick{
		int x;
		int y;
		public chick(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static int size,arr[][],cnt,v[],remain;
	public static chick[] remainarr;
	public static ArrayList<chick> b;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split(" ");
		size = Integer.parseInt( str[0] );
		remain = Integer.parseInt( str[1] );
		arr = new int[size][size];
		cnt=0;
		b = new ArrayList<chick>();
		for(int m=0;m<size;m++) {
			String s[] = br.readLine().split(" ");
			for(int n=0;n<size;n++) {
				arr[m][n] = Integer.parseInt(s[n]);
				if(arr[m][n]==2) {
					cnt++;
					b.add(new chick(m,n));
				}
			}
		}
		remainarr = new chick[remain];
		v = new int[cnt];
		min = Integer.MAX_VALUE;
		facto(0,0);
		System.out.println(min);
	}
	private static void facto(int start, int count) {
		if(count==remain) {
			checklen(remainarr);
		}
		else {
			for(int i=0;i<cnt;i++) {
				if(v[i]==0) {
					v[i]=1;
					remainarr[count]=b.get(i);
					facto(i,count+1);
					v[i]=0;
				}
			}
		}
	}
	
	private static void checklen(chick[] pop) {
		int total_len=0;
		for(int m=0;m<size;m++) {
			for(int n=0;n<size;n++) {
				if(arr[m][n]==1) {
					int len=999;
					for(int z=0;z<pop.length;z++) {
						int now=Math.abs(pop[z].x-m)+Math.abs(pop[z].y-n);
						if(len>now) len=now;
					}
					total_len+=len;
				}
			}
		}
		if(total_len<min) min = total_len;
	}
	public static int min;
}

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

문제

문제

출처

ICPC

시간초과(Java코드포함)

fastz 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말