21.09.02 [백준] 1197 최소 스패닝 트리 - 최소신장 트리 / 크루스칼 알고리즘

문제

아이디어

간선의 크기가 가장 작은 것을 뽑는다.
선택한 간선의 두 정점이 같은 그룹인지 비교
2-1. 같은 그룹이면 skip
2-2. 다른 그룹이면 같은 그룹으로 만들고, 선택한 간선을 최소 신장 트리에 추가
1~2를 반복하고, 최소 신장 트리에 V-1개 간선이 선택되면 종료

어려운점 & 실수

정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * 3 3
 * 1 2 1
 * 2 3 2
 * 1 3 3
 */
public class N1197 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        // 비방향 연결 그래프
        PriorityQueue<Node> graph = new PriorityQueue<>();
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());
            graph.add(new Node(a, b, edge));
        }

        int result = spanningKruskal(V, graph);
        System.out.println(result);
    }

    private static int spanningKruskal(final int v, final PriorityQueue<Node> graph) {
        // 그룹(부모)정보 저장 - 같은 그룹인지 확인용
        int[] parent = new int[v + 1];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i; //자기 자신의 그룹에 속하도록 초기화
        }

        int result = 0;
        int cnt = 0;
        while (!graph.isEmpty()) {
            Node node = graph.poll();
            if(isEqualParent(parent, node.a, node.b)) {
               continue;
            }
            result += node.cost;
            cnt++;
            union(parent, node.a, node.b);
            if (cnt == v - 1) break;
        }
        return result;
    }

    public static void union(int[] parent, int prev, int cur) {
        int prevParent = getParent(parent, prev);
        int curParent = getParent(parent, cur);
        if (prevParent <= curParent) {
            parent[curParent] = prevParent;
        } else {
            parent[prevParent] = curParent;
        }
    }

    public static boolean isEqualParent(int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
        return a == b;
    }

    private static int getParent(final int[] parent, final int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = getParent(parent, parent[x]);
    }

    static class Node implements Comparable<Node> {
        int a;
        int b;
        int cost;

        public Node(final int a, final int b, final int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }

        @Override
        public int compareTo(final Node o) {
            return cost - o.cost;
        }
    }
}

최적화

우선순위 큐를 이용해서 가중치에 따라서 뽑혀나오도록 함
union에서 랭크를 이용한 최적화

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

public class Main {

	static class Node implements Comparable<Node> {
		int u, v, w;	// vertex num, vertex_connected num, weight
		Node( int u, int v, int w ) {
			this.u = u;
			this.v = v;
			this.w = w;
		}
		@Override
		public int compareTo( Node o ) {
			return w - o.w;
		}
	}
	
	public static int spanning_kruskal( PriorityQueue<Node> e, int n ) {
		int w_sum = 0, i, t = 0, u, v, w;
		int p[] = new int[n], r[] = new int[n];
		for( i = 0; i < n; i++ )  // make set
			p[i] = i;
		while( t < n-1 && !e.isEmpty() ) {
			Node nd = e.remove();
			u = nd.u; v = nd.v; w = nd.w;
			if( find( u, p ) != find( v, p ) ) {  // find set
				w_sum += w;
				union( u, v, p, r );  // union set
				t++;
			}
		}
		return w_sum;
	}
	public static int find( int n, int p[] ) {  // 경로 압축 최적화
		if( n == p[n] ) 
			return n;
		return p[n] = find( p[n], p );
	}
	public static void union( int a, int b, int p[], int r[] ) {  // 랭크를 이용한 최적화
		a = find( a, p );
		b = find( b, p );
		if( r[a] > r[b] )
			p[b] = a;
		else {
			p[a] = b; 
			if( r[a] == r[b] )
				r[b]++;
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n, m, a, b, c, i;
		StringTokenizer st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		PriorityQueue<Node> e = new PriorityQueue<>(); // edge
		for( i = 0; i < m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			a = Integer.parseInt( st.nextToken() ) - 1;	// u
			b = Integer.parseInt( st.nextToken() ) - 1;	// v
			c = Integer.parseInt( st.nextToken() );		// w
			e.add( new Node( a, b, c ) );
		}
		br.close();
		System.out.println( spanning_kruskal( e, n ) );
		
	}
}

수정전 코드

package dev.solar.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

/**
 * 3 3
 * 1 2 1
 * 2 3 2
 * 1 3 3
 */
public class N1197 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int[] parent = new int[V + 1]; //같은 그룹인지 확인
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i; //자기 자신의 그룹에 속하도록 초기화
        }

        // 비방향 연결 그래프
        ArrayList<Node> graph = new ArrayList<>(E);
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());
            graph.add(new Node(a, b, edge));
        }

        // 간선 저장 - 가충치 오름차순 정렬 필요
        Collections.sort(graph, Comparator.comparing(node -> node.cost));

        int result = 0;
        int cnt = 0;
        for (Node node : graph) {
            if(isEqualParent(parent, node.a, node.b)) {
               continue;
            }
            result += node.cost;
            cnt++;
            union(parent, node.a, node.b);
            if (cnt == V - 1) break;
        }
        System.out.println(result);
    }

    public static void union(int[] parent, int prev, int cur) {
        int prevParent = getParent(parent, prev);
        int curParent = getParent(parent, cur);
        if (prevParent <= curParent) {
            parent[curParent] = prevParent;
        } else {
            parent[prevParent] = curParent;
        }
    }

    public static boolean isEqualParent(int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
        return a == b;
    }

    private static int getParent(final int[] parent, final int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = getParent(parent, parent[x]);
    }

    static class Node {
        int a;
        int b;
        int cost;

        public Node(final int a, final int b, final int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
    }
}

[BJ] 1197 최소 스패팅 트리 - 최적화

[BJ] 1197 최소 스패팅 트리 - 최적화 - rank

Navigation Menu

Repository navigation

21.09.02 [백준] 1197 최소 스패닝 트리 - 최소신장 트리 / 크루스칼 알고리즘 #297

아이디어

어려운점 & 실수

정답

최적화

수정전 코드

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

21.09.02 [백준] 1197 최소 스패닝 트리 - 최소신장 트리 / 크루스칼 알고리즘 #297

Description

아이디어

어려운점 & 실수

정답

Activity

blossun commented on Sep 2, 2021

최적화

blossun commented on Sep 2, 2021

수정전 코드

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions