강승현입니다
article thumbnail
Published 2021. 3. 27. 18:36
백준 6497 전력난 java OnlineJudge
반응형

문제로이동


목차

     



    문제 설명

    일반적인 최소스패닝 트리(MST) 문제입니다.

    크루스칼 알고리즘과 프림 알고리즘으로 해결해봤습니다.

     


    런타임 에러1

    이 문제는 테스트 케이스가 여러개 들어옵니다. 마지막 0 0 입력이 왜 있는가 했더니,,

    결국 이 문제점을 뒤늦게 이해하고 코드 수정을 하여 AC를 받았습니다.

    즉, 0 0이 입력되기 전까지 테스트 케이스가 무한대로 들어오니 M,N 값을 검증해야 합니다.

     

    if(M==0 && N==0)
    	return;

    런타임 에러2

    전혀 생각지 못했던 이유였습니다.

    하단 소스코드엔 while문 밖으로 선언되어 있지만 아래처럼 while문 내에 삽입했더니 발생했습니다.

     

    while(true){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //Your Code
    }

     

    위와 같이 BufferedReader 선언을 반복문 내에 넣었더니 계속해서 ArrayIndexOutOfBounds가 발생합니다.

    늘 새로운 상황의 에러가 저를 반겨주니 감개무량하네요.

    이 에러도 정확한 원인을 파악해보고 수정하도록 하겠습니다.


    소스 코드

    Java8 크루스칼

    import java.util.*;
    import java.io.*;
    
    public class Main_kruskal {
    	static StringBuilder sb = new StringBuilder();
    	static int N,M,parent[];
    	static int getParent(int x) {
    		if(parent[x] == x)return x;
    		return parent[x] = getParent(parent[x]);
    	}
    	static void unionParent(int a,int b) {
    		a = getParent(a);
    		b = getParent(b);
    		if(a<b)parent[b]=a;
    		else parent[a]=b;
    	}
    	static void input() throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st;
    		while(true) {
    			st = new StringTokenizer(br.readLine());
    			M = Integer.parseInt(st.nextToken());//집의수
    			N = Integer.parseInt(st.nextToken());//길의수
    			if(M==0 && N==0)break;
    			parent = new int[M];
    			for(int i =0;i<M;i++)parent[i]=i;
    			class Edge{
    				int from,to,dist;
    				public Edge(int from, int to, int dist) {this.from = from;this.to = to;this.dist = dist;}			
    			}
    			ArrayList<Edge> query = new ArrayList<>();
    			int total = 0;
    			for(int i=0;i<N;i++) {//길의 정보
    				st = new StringTokenizer(br.readLine());
    				int a = Integer.parseInt(st.nextToken());
    				int b = Integer.parseInt(st.nextToken());
    				int d = Integer.parseInt(st.nextToken());
    				total+=d;
    				query.add(new Edge(a,b,d));
    			}
    			Collections.sort(query,(o1,o2)->o1.dist-o2.dist);
    			int answer =0;
    			for(Edge edge:query) {
    				int a = edge.from;
    				int b = edge.to;
    				if(getParent(a)==getParent(b))continue;
    				unionParent(a,b);
    				answer+=edge.dist;
    			}
    			sb.append(total-answer).append("\n");
    		}		
    	}
    
    	public static void main(String[] args) throws IOException {
    		input();
    		System.out.println(sb);
    	}
    }

    Java8 프림

    import java.util.*;
    import java.io.*;
    
    public class Main_Prim {
    	static StringBuilder sb = new StringBuilder();
    	static int N,M;
    	static boolean visited[];
    	static class Edge implements Comparable<Edge>{
    		int node,dist;
    		public Edge(int node, int dist) {this.node = node;this.dist = dist;}
    		@Override
    		public int compareTo(Edge o) {			
    			return this.dist-o.dist;
    		}		
    	}
    	static void input() throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st;
    		while(true) {
    			st = new StringTokenizer(br.readLine());
    			M = Integer.parseInt(st.nextToken());//집의수
    			N = Integer.parseInt(st.nextToken());//길의수
    			if(M==0 && N==0)break;
    			visited = new boolean[M];
    			ArrayList<ArrayList<Edge>> query = new ArrayList<>();
    			for(int i =0;i<M;i++)query.add(new ArrayList<>());
    			int totalCost = 0;
    			for(int i=0;i<N;i++) {//길의 정보
    				st = new StringTokenizer(br.readLine());
    				int a = Integer.parseInt(st.nextToken());
    				int b = Integer.parseInt(st.nextToken());
    				int d = Integer.parseInt(st.nextToken());
    				totalCost+=d;
    				query.get(a).add(new Edge(b,d));
    				query.get(b).add(new Edge(a,d));
    			}
    			PriorityQueue<Edge> pq = new PriorityQueue<>();
    			for(Edge cur:query.get(0))
    				pq.add(cur);//임의의 정점 0부터 시작한다.
    			visited[0]=true;
    			int minCost =0;
    			while(!pq.isEmpty()) {
    				Edge edge = pq.poll();
    				if(visited[edge.node])continue;//이미 방문했다면
    				visited[edge.node]=true;				
    				minCost+=edge.dist;				
    				for(Edge next:query.get(edge.node)) {
    					pq.add(next);//다음 pq에 추가
    				}
    			}
    			sb.append(totalCost-minCost).append("\n");
    		}		
    	}
    
    	public static void main(String[] args) throws IOException {
    		input();
    		System.out.println(sb);
    	}
    }
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    profile on loading

    Loading...