글 읽기 - 최적인것같은데 시간초과가 나는 이유를 모르겠습니다.

kdh9520 9년 전 1

셋에 포함된 (체크된)애들은 포문도 안돌고 함수도 수행안되게 했는데도 시간초과가뜹니다.

이이상 최적화시킬수 없는거같은데 어떤부분이 문제인지 모르겠네요...자바로해서 시간초과뜨는건가..

import java.util.*;
import java.util.concurrent.*;

class Main {
	private static int[][] enemyInfo;
	private static int numOfEnemy;
	private static boolean[] isInSet;

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);

		int testcaseN = keyboard.nextInt();

		for (int i = 0; i < testcaseN; i++) {
			numOfEnemy = keyboard.nextInt();

			enemyInfo = new int[numOfEnemy][3];

			for (int j = 0; j < numOfEnemy; j++) {
				enemyInfo[j][0] = keyboard.nextInt();
				enemyInfo[j][1] = keyboard.nextInt();
				enemyInfo[j][2] = keyboard.nextInt();
			}

			isInSet = new boolean[numOfEnemy];
			int count = 0;

			for (int j = 0; j < numOfEnemy; j++) {
				if (isInSet[j] == false) {
					search(j);
					count++;
				}
			}
			System.out.println(count);
		}

	}

	// 해당 index에서 통신가능한(체크되지않은 것 들 중) 모든것들을 체크
	private static void search(int that) {
		if (isInSet[that])
			return;
		else {
			isInSet[that] = true;

			for (int j = 0; j < numOfEnemy; j++) {
				if (isInSet[j] == false) {
					double rSum = enemyInfo[that][2] + enemyInfo[j][2];
					double mtom = Math
							.sqrt(Math.pow(
									enemyInfo[that][0] - enemyInfo[j][0], 2)
									+ Math.pow(enemyInfo[that][1]
											- enemyInfo[j][1], 2));
					if (mtom <= rSum)// 통신가능
					{
						search(j);
					}
				}
			}

			return;
		}
	}
}

kdh9520 9년 전 0

인접리스트를 어떤형식으로 유지하셨나요?

kdh9520 9년 전 0

AC받았다는말이 어떤건지 설명좀 해주실수있나요??ㅜ

kdh9520 9년 전 0

죄송한데 코드좀 볼수 있을까요 ?ㅠㅠ

첨에 인접리스트 구성할때도 for문2번 중첩시켜서 돌려야하지않나요?

kdh9520 9년 전 0

같은방식으로 코딩했는데도 시간초과이네요...

코드에 문제가있나요 혹시?ㅠㅠ

import java.util.*;
import java.util.concurrent.*;

class Main {
	private static int[][] enemyInfo;
	private static Vector<Integer>[] adjustInfo;
	private static int numOfEnemy;
	private static boolean[] traveled;

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);

		int testcaseN = keyboard.nextInt();

		for (int i = 0; i < testcaseN; i++) {
			numOfEnemy = keyboard.nextInt();

			enemyInfo = new int[numOfEnemy][3];

			for (int j = 0; j < numOfEnemy; j++) {
				enemyInfo[j][0] = keyboard.nextInt();
				enemyInfo[j][1] = keyboard.nextInt();
				enemyInfo[j][2] = keyboard.nextInt();
			}

			// 인접리스트 구성
			adjustInfo = new Vector[numOfEnemy];
			Arrays.fill(adjustInfo, new Vector<Integer>());
			for (int j = 0; j < numOfEnemy; j++) {
				for (int k = j+1; k < numOfEnemy; k++) {
					if (isSet(j, k)) {
						adjustInfo[j].add(k);
						adjustInfo[k].add(j);
					}
				}
			}

			int count = 0;
			traveled = new boolean[numOfEnemy];
			
			for (int j = 0; j < numOfEnemy; j++) {
				if(traveled[j]==true)
					continue;
				
				dfs(j);
				count++;
			}
			System.out.println(count);
		}

	}

	// dfs로 방문
	private static void dfs(int that) {
		traveled[that]=true;
		
		for(int i = 0 ; i<adjustInfo[that].size();i++){
			if(traveled[adjustInfo[that].get(i)] == false)
				dfs(adjustInfo[that].get(i));
		}
		return;
	}

	private static boolean isSet(int that, int target) {
		double rSum = enemyInfo[that][2] + enemyInfo[target][2];
		double mtom = Math.sqrt(Math.pow(enemyInfo[that][0]
				- enemyInfo[target][0], 2)
				+ Math.pow(enemyInfo[that][1] - enemyInfo[target][1], 2));
		if (mtom <= rSum)// 통신가능
			return true;
		else
			return false;
	}
}

kdh9520 9년 전 0

거리판단은 double형으로 해줘야하지않나요?

소수점이 날라가면 계산오류가날수도있으니... 그렇게했는데

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

문제

문제

출처

ICPC

최적인것같은데 시간초과가 나는 이유를 모르겠습니다.

kdh9520 9년 전 1

kdh9520 9년 전 0

kdh9520 9년 전 0

kdh9520 9년 전 0

kdh9520 9년 전 0

kdh9520 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말