글 읽기 - 60% 정도에서 틀렸다고 뜹니다

y_y22 2년 전 0

mst 문제길래 크루스칼 알고리즘 이용해서 풀었는데 테케는 다 맞는데 60퍼 정도에서 틀렸다고 뜹니다.. 이유가 무엇일까요?!

package week25.boj16398;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] parents;
	static List<Edge> edgeList = new ArrayList<>();
	static class Edge implements Comparable<Edge>{
		int from;
		int to;
		int weight;
		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return this.weight - o.weight;
		}
	}
	static int find(int a) {
		if(parents[a]==a) {
			return a;
		}
		
		return parents[a] = find(parents[a]);
	}
	static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot == bRoot) {
			return false;
		}
		
		parents[bRoot] = aRoot;
		
		return true;
	}
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		parents = new int[N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int weight = Integer.parseInt(st.nextToken());
				edgeList.add(new Edge(i,j,weight));
			}
		}
		
		for(int i=0; i<N; i++) {
			parents[i] = i;
		}
		
		Collections.sort(edgeList);
		
		int result = 0;
		int count = 0;
		
		for (Edge e : edgeList) {
			if(union(e.from, e.to)){
				result += e.weight;
				
				if(++count == N-1)	break;
			}
		}
		System.out.println(result);

	}

}

rlaskawn0920 2년 전 5

정답이 int형 범위를 넘어갈수 있어서.. result를 long으로 선언하시면 될거에요!

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

문제

문제

출처

ICPC

60% 정도에서 틀렸다고 뜹니다

y_y22 2년 전 0

rlaskawn0920 2년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말