글 읽기 - x,y,z좌표 정렬하여 i/i+1 행성간 간선구하여 Kruskal구성

naegeora 7년 전 0

x,y,z좌표 정렬하여 i/i+1 행성간 간선구하여

Kruskal로 최소 스패인트리 돌리는데

17%에서 run time error 이 납니다.....

고수님들의 조언 부탁합니다.

잘못된 부분을 못찾겠습니다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class baekjoon_2887_행성터널 {

	static public class comp_x implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			// TODO Auto-generated method stub
			if(o1[0]-o2[0]>0)return 1;
			else return -1;
		}

	}
	static public class comp_y implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			// TODO Auto-generated method stub
			if(o1[1]-o2[1]>0) return 1;
			else return -1;
		}

	}
	static public class comp_z implements Comparator<int[]> {

		@Override
		public int compare(int[] o1, int[] o2) {
			// TODO Auto-generated method stub
			if(o1[2]-o2[2]>0)return 1;
			else return -1;
		}

	}
	static public class Element implements Comparable<Element>{
		int v1; int v2;int cost;
		Element(int v1,int v2, int cost){
			this.v1=v1;
			this.v2=v2;
			this.cost=cost;
		}
		@Override
		public int compareTo(Element o) {
			// TODO Auto-generated method stub
			if (cost-o.cost>0) return 1;
			else return -1;
		}
	}

	static int N;
	static long answer;
	static int[] C;
	static int[][] pos;
	static Element[] list;

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		long start=System.currentTimeMillis();
		System.setIn(new FileInputStream("res/baekjoon_2887_행성터널.txt"));
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		String[] splits;
		N=Integer.parseInt(br.readLine());	
		pos=new int[N+1][4];
		C=new int[N+1];
		for(int i=1;i<=N;i++)C[i]=i;//그룹의 대표값 초기화

		for(int i=1;i<=N;i++){
			splits=br.readLine().split(" ");
			pos[i][0]=Integer.parseInt(splits[0]);	//x좌표
			pos[i][1]=Integer.parseInt(splits[1]);    //y
			pos[i][2]=Integer.parseInt(splits[2]);	//z
			pos[i][3]=i;		//행성번호
		}	

		list=new Element[3*N+1];
		int idx=0;

		Comparator<int[]> comp_x=new comp_x();
		Arrays.sort(pos,1,N+1,comp_x);	
		for(int i=1;i<N;i++) list[idx++]=new Element(pos[i][3],pos[i+1][3],pos[i+1][0]-pos[i][0]);
		Comparator<int[]> comp_y=new comp_y();
		Arrays.sort(pos,1,N+1,comp_y);	
		for(int i=1;i<N;i++) list[idx++]=new Element(pos[i][3],pos[i+1][3],pos[i+1][1]-pos[i][1]);
		Comparator<int[]> comp_z=new comp_z();
		Arrays.sort(pos,1,N+1,comp_z);	
		for(int i=1;i<N;i++) list[idx++]=new Element(pos[i][3],pos[i+1][3],pos[i+1][2]-pos[i][2]);

		Arrays.sort(list,0,idx);//오름차순정렬
		//System.out.println(idx);
		
		int cnt=0;
		for(int i=0;i<idx;i++){
			int a=list[i].v1; int b=list[i].v2; int c=list[i].cost;
			int ca=uf(a); int cb=uf(b); 
			if(ca!=cb){
				answer+=c;
				C[ca]=cb;
				if(cnt++==N-1) break;
			}
		}

		System.out.println(answer);	

		//System.out.println(System.currentTimeMillis()-start+" msec elapsed.");
		br.close();
	}

	public static int uf(int x) {
		// TODO Auto-generated method stub
		if(C[x]==x)return x;
		C[x]=uf(C[x]);
		return C[x];
	}
}

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

문제

문제

출처

ICPC

x,y,z좌표 정렬하여 i/i+1 행성간 간선구하여 Kruskal구성

naegeora 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말