글 읽기 - 우선순위 큐로 구현하면 왜 틀렸다고 나오는지 궁금합니다.

tkdgur8377 3년 전 0

질문한 소스는 우선순위 큐를 사용해서 구현했습니다.

우선순위 큐부분만 arraylist로 바꿔서 다시 정렬해서 돌리면 통과하던데

왜그런지 궁금합니다ㅜ ㅜ

package package29;

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

public class main {
	static int N;
	static Vertex[] vertexs;
	static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
	static int[] parent; 
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		N = Integer.parseInt(br.readLine()); 
		vertexs = new Vertex[N]; 
		
		StringTokenizer st; 
		for (int i = 0; i < N ; i++) { 
			st = new StringTokenizer(br.readLine().trim(), " ");
			int X = stoi(st.nextToken()); 
			int Y = stoi(st.nextToken());
			int Z = stoi(st.nextToken()); 
			vertexs[i] = new Vertex(X, Y, Z, i);
		} 
		
		Arrays.sort(vertexs,new Comparator<Vertex>() {
			@Override
			public int compare(Vertex o1, Vertex o2) {
				return Integer.compare(o1.x, o2.x);
			}
		});
		for (int i = 1; i <N ; i++) {
			pq.add(new Edge(vertexs[i-1].id, vertexs[i].id, Math.abs(vertexs[i].x-vertexs[i-1].x)));
		}
			
		Arrays.sort(vertexs,new Comparator<Vertex>() {
			@Override
			public int compare(Vertex o1, Vertex o2) {
				return Integer.compare(o1.y, o2.y);
			}
		});
		for (int i = 1; i <N ; i++) {
			pq.add(new Edge(vertexs[i-1].id, vertexs[i].id, Math.abs(vertexs[i].y-vertexs[i-1].y)));
		} 
		
		Arrays.sort(vertexs,new Comparator<Vertex>() {
			@Override
			public int compare(Vertex o1, Vertex o2) {
				return Integer.compare(o1.z, o2.z);
			}
		});
		for (int i = 1; i <N ; i++) {
			pq.add(new Edge(vertexs[i-1].id, vertexs[i].id, Math.abs(vertexs[i].z-vertexs[i-1].z)));
		} 
		
		
		parent = new int[N+1];
		for (int i = 1; i <= N ; i++)
			parent[i] = i; 
		long result=0;
		
		for (Edge ed: pq) {
			if(union(ed.s, ed.e)) { 
				result += ed.w; 
			} 
		}
		System.out.println(result);
	}
	
	static class Vertex {
		int x, y, z, id;
		Vertex(int x, int y, int z, int id) {
			this.x = x;
			this.y = y;
			this.z = z;
			this.id = id;
		}
	}
	
	static class Edge implements Comparable<Edge> {
		int s, e, w;
		Edge(int s, int e, int w) {
			this.s = s; 
			this.e = e; 
			this.w = w;
		} 
		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.w, o.w);
		}
	} 
	
	public static int find_parent(int num) {
		if(parent[num] != num)
			return parent[num] = find_parent(parent[num]);
		return parent[num];
	}
	
	public static boolean union(int a, int b) {
		a = find_parent(a);
		b = find_parent(b);
		
		if(a==b) {
			return false;
		}
		else if(a < b)
			parent[b] = a;
		else
			parent[a] = b;
		return true;
	}
	public static int stoi(String string) {
		return Integer.parseInt(string);
	}
}

tkdgur8377 3년 전 0

통과한 소스는 아래와 같습니다.

package package29;

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

public class num2887 {
	static int N;
	static Vertex[] vertexs;
	static ArrayList<Edge> edges;
	static int[] parent; 
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		N = Integer.parseInt(br.readLine()); 
		vertexs = new Vertex[N]; 
		edges = new ArrayList<>(); 
		StringTokenizer st; 
		for (int i = 0; i < N ; i++) { 
			st = new StringTokenizer(br.readLine().trim(), " ");
			int X = stoi(st.nextToken()); 
			int Y = stoi(st.nextToken());
			int Z = stoi(st.nextToken()); 
			vertexs[i] = new Vertex(X, Y, Z, i);
		} 
		
		Arrays.sort(vertexs,new Comparator<Vertex>() {
			@Override
			public int compare(Vertex o1, Vertex o2) {
				return Integer.compare(o1.x, o2.x);
			}
		});
		for (int i = 1; i <N ; i++) {
			edges.add(new Edge(vertexs[i-1].id, vertexs[i].id, Math.abs(vertexs[i].x-vertexs[i-1].x)));
		}
			
		Arrays.sort(vertexs,new Comparator<Vertex>() {
			@Override
			public int compare(Vertex o1, Vertex o2) {
				return Integer.compare(o1.y, o2.y);
			}
		});
		for (int i = 1; i <N ; i++) {
			edges.add(new Edge(vertexs[i-1].id, vertexs[i].id, Math.abs(vertexs[i].y-vertexs[i-1].y)));
		} 
		
		Arrays.sort(vertexs,new Comparator<Vertex>() {
			@Override
			public int compare(Vertex o1, Vertex o2) {
				return Integer.compare(o1.z, o2.z);
			}
		});
		for (int i = 1; i <N ; i++) {
			edges.add(new Edge(vertexs[i-1].id, vertexs[i].id, Math.abs(vertexs[i].z-vertexs[i-1].z)));
		} 
			
		Collections.sort(edges,new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return Integer.compare(o1.w, o2.w);
			}
		});
		
		parent = new int[N+1];
		for (int i = 1; i <= N ; i++)
			parent[i] = i; 
		long result=0;
		
		for (Edge ed:edges) {
			if(union(ed.s, ed.e)) { 
				result += ed.w; 
			} 
		}
		System.out.println(result);
	}
	
	static class Vertex {
		int x, y, z, id;
		Vertex(int x, int y, int z, int id) {
			this.x = x;
			this.y = y;
			this.z = z;
			this.id = id;
		}
	}
	
	static class Edge {
		int s, e, w;
		Edge(int s, int e, int w) {
			this.s = s; 
			this.e = e; 
			this.w = w;
		} 
	} 
	
	public static int find_parent(int num) {
		if(parent[num] != num)
			return parent[num] = find_parent(parent[num]);
		return parent[num];
	}
	
	public static boolean union(int a, int b) {
		a = find_parent(a);
		b = find_parent(b);
		if(a==b)
			return false;
		parent[b] = a;
		return true;
	}
	public static int stoi(String string) {
		return Integer.parseInt(string);
	}
}

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

문제

문제

출처

ICPC

우선순위 큐로 구현하면 왜 틀렸다고 나오는지 궁금합니다.

tkdgur8377 3년 전 0

tkdgur8377 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말