글 읽기 - 시간초과 질문입니다

tjgy9023 5년 전 0

백트래킹을 이용해서 M개 만 남기고 지우는 방식으로 구현을 했는데

값은 잘나오는데 마지막게 되게 느리게 나오더라구요

치킨집을 M개로 만들고 집 하나씩 치킨집 M개와의 거리로 최소값 구해서

더해주는 방식으로 했는데 어떻게 보면 4중포문인데

어디를 잡아야 복잡도가 떨어질지 감이 안잡히네요..

처음에 최소 거리잡는 걸 bfs로 할려고 했는데 이게 오히려 더 오래 걸릴 것 같아서 아래처럼 만들었는데 더 걸리는건가..

public class Main {
	
	public static int[][] arr;
	public static ArrayList<Coordinate> dir;
	public static ArrayList<String> twodir;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int countCk = 0;
		
		dir = new ArrayList<>();
		twodir = new ArrayList<>();
		arr = new int[N][N];
		for(int i = 0; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N ; j ++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
				if(arr[i][j] == 2) { 
					countCk++;
					twodir.add(i+""+j);
				}
				if(arr[i][j] == 1) dir.add(new Coordinate(i, j));
			}
		}
		chickenHouse(0, countCk-M, N);
		System.out.println(min);
		
	}
	static int min = Integer.MAX_VALUE;
	
	public static ArrayList<String> remlist = new ArrayList<>();	
	public static void chickenHouse(int cnt, int M, int N) {
		
		if(cnt == M) {
			int total = 0;
			for(Coordinate co: dir) {
				total += chickDis(N, co);
			}
			
			if(min > total) {
				min = total;
			}
		}
		
		
		for(int i = 0; i < N ; i++ ) {
			for(int j = 0; j < N; j++) {
				if(arr[i][j] == 2) {
					arr[i][j] = 0;
					remlist.add(i+""+j);
					chickenHouse(cnt + 1, M, N);
					arr[i][j] = 2;
					remlist.remove(i+""+j);
				}
			}
		}
		
	}
	
	
	public static int chickDis(int N, Coordinate co) {
		int min = Integer.MAX_VALUE;
		int x = co.x;
		int y = co.y;
		
		for(String str : twodir) {
			if(!remlist.contains(str)) {
				int dis = Math.abs((str.charAt(0)-'0') - x)
						+ Math.abs((str.charAt(1)-'0') - y);
				if(min > dis) min = dis;
			}
		}
		
		return min;
	}
	
}
class Coordinate{
	int x;
	int y;
	public Coordinate(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

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

문제

문제

출처

ICPC

시간초과 질문입니다

tjgy9023 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말