글 읽기 - 자바 시간초과

kmn4555 4년 전 0

채점 시작하자마자 시간초과로 채점이 안되네요 ㅠㅠ 왜이럴까요 ㅠㅠ

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static String[] str;
	
	static int n,m;
	
	static int map[][];
	static boolean visit[];
	
	static int c_len[][];
	
	static int home = 0;
	static int chicken = 0;
	
	static int min = 1000000000;
	
	static ArrayList<Integer> h = new ArrayList<Integer>();
	static ArrayList<Integer> c = new ArrayList<Integer>();

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		str = bfr.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		m = Integer.parseInt(str[1]);
		
		map = new int[n][n];
		
        //치킨집과 집의 좌표를 linkedlist에 저장
		for(int i = 0; i < n; i++) {
			str = bfr.readLine().split(" ");
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if(map[i][j] == 1){
					home++;
					h.add(i);
					h.add(j);
				}
				else if(map[i][j] == 2){
					chicken++;
					c.add(i);
					c.add(j);
				}
			}
		}
		
		c_len = new int[home][chicken];
		visit = new boolean[chicken];
		
        //모든 집의 치킨 거리 계산
		for(int i = 0; i < home; i++) {
			for(int j = 0; j < chicken; j++)
				c_len[i][j] = abs(h.get(i*2) , c.get(j*2)) + abs(h.get(i*2 + 1) , c.get(j*2 + 1));
		}
		
		for(int i = 0; i < (chicken); i++) {
			dfs(0, i, 0, 0);
		}
		
		bfw.write(min + "");
		bfw.flush();

	}
	
	static void dfs(int level, int num, int cnt, int len) throws IOException {
        //지금까지 사용한 치킨집의 개수가 m개 초과하면 return
		if(!visit[num]) {
			cnt++;
			if(cnt > m)
				return;
			visit[num] = true;
		}
		
        //모든 집을 다 탐색했으면 최소 비교
		if((level == home-1)) {
			len += c_len[level][num];
			min = min > len ? len : min;
			visit[num] = false;
			return;
		}
		
		len += c_len[level][num];
		
		for(int i = 0; i < chicken; i++) {
			dfs(level+1, i, cnt, len);
		}
		
		visit[num] = false;
	}
	
	static int abs(int a, int b) {
		return (a - b) > 0 ? (a - b) : (b - a);
	}

}

djm03178 4년 전 1

단순히 M개를 뽑는 것은 순서가 중요하지 않으므로 순서를 정해놓고 뽑으면 되는데, 이 코드에서는 88번째 줄처럼 순서를 바꾸어 뽑는 경우를 전부 해보고 있으므로 최악의 경우 13! 개의 조합을 해보게 됩니다.

kmn4555 4년 전 0

그러면 어떤 방식으로 고치면 좋을까요 ... ㅠ?

djm03178 4년 전 0

i번째까지 뽑아봤다면 i+1번째 이후에서 다음 뽑을 것을 찾으면 됩니다.

kmn4555 4년 전 0

이렇게 맨 처음 dfs들어갔을때 값을 주면서 for문을 그 문장부터 시작하도록 바꿨는데도 시간초과가 나는데, 이게 방법이 아닌건가요?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
	static BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static String[] str;
	
	static int n,m;
	
	static int map[][];
	static boolean visit[];
	
	static int c_len[][];
	
	static int home = 0;
	static int chicken = 0;
	
	static int min = 1000000000;
	
	static ArrayList<Integer> h = new ArrayList<Integer>();
	static ArrayList<Integer> c = new ArrayList<Integer>();

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		str = bfr.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		m = Integer.parseInt(str[1]);
		
		map = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			str = bfr.readLine().split(" ");
			for(int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(str[j]);
				if(map[i][j] == 1){
					home++;
					h.add(i);
					h.add(j);
				}
				else if(map[i][j] == 2){
					chicken++;
					c.add(i);
					c.add(j);
				}
			}
		}
		
		c_len = new int[home][chicken];
		visit = new boolean[chicken];
		
		for(int i = 0; i < home; i++) {
			for(int j = 0; j < chicken; j++)
				c_len[i][j] = abs(h.get(i*2) , c.get(j*2)) + abs(h.get(i*2 + 1) , c.get(j*2 + 1));
		}
		
		for(int i = 0; i <= (chicken - m); i++) {
			dfs(0, i, 0, 0, i);
		}
		
		bfw.write(min + "");
		bfw.flush();

	}
	
	static void dfs(int level, int num, int cnt, int len, int k) throws IOException {
		if(!visit[num]) {
			cnt++;
			if(cnt > m)
				return;
			visit[num] = true;
		}
		
		if((level == home-1)) {
			len += c_len[level][num];
			min = min > len ? len : min;
			visit[num] = false;
			return;
		}
		
		len += c_len[level][num];
		
		for(int i = k; i < chicken; i++) {
			dfs(level+1, i, cnt, len, k);
		}
		
		visit[num] = false;
	}
	
	static int abs(int a, int b) {
		return (a - b) > 0 ? (a - b) : (b - a);
	}

}

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

문제

문제

출처

ICPC

자바 시간초과

kmn4555 4년 전 0

djm03178 4년 전 1

kmn4555 4년 전 0

djm03178 4년 전 0

kmn4555 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말