[백준/G3/MST/자바] 14621 나만 안되는 연애

💡 문제

 

깽미는 24살 모태솔로이다.

깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다.

미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.

이 앱은 사용자들을 위해 사심 경로를 제공한다.

이 경로는 3가지 특징을 가지고 있다.

1. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.
2. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.
3. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다.

 

만약 도로 데이터가 만약 위의 그림과 같다면,

오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 조건을 만족하는 경로를 만들 수 있다.

이때, 주어지는 거리 데이터를 이용하여 사심 경로의 길이를 구해보자.

 

⌨ 입력

 

첫째 줄 정수 학교의 수 N 도로의 수 M ( 2 <= N <= 1000 ) ( 1 <= M <= 10000 )

두번째 줄 학교가 남초 대학교일 경우 M 여초 대학교 라면 W

M개의 줄에 u v d ( u = 출발,  v = 도착,  d = 거리 ) ( 1 <= u,v <= N ) ( 1 <= d <= 1000 )

 

💻 출력 / 제한

 

깽미가 만든 앱의 경로 길이를 출력 한다 ( 연결 불가능 할 경우 -1 출력 )

 

---

 

풀이 방법

 

문제 유형 : 최소 스패닝 트리

 

 

최소 스패닝 트리란?

 

스패닝 트리

1 - N 까지의 정점이 있을 때, 싸이클 없이 정점을 모두 연결 하는 트리

 

최소 스패닝 트리

가중치가 있을때 ( 거리, 비용 ) 스패닝 트리를 가장 적은 가중치로 완성 하는 트리

 

 

예시 ) 스패닝 트리

 

 

최소 스패닝 트리를 구현 하는 알고리즘

 

프림 알고리즘

정점의 정보를 통해 최소 스패닝 트리를 구현 하는 알고리즘

 

크루스칼 알고리즘

간선의 정보를 통해 최소 스패닝 트리를 구현 하는 알고리즘

시간 복잡도 :
간선의 수가 N개 일때 정렬 하는 것이 가장 큰 시간 복잡도 이므르 N log N 입니다.
list.sort() 를 사용할 경우 timeSort 방식( 병합 정렬, 삽입 정렬을 활용 한 정렬 )의
시간 복잡도 N log N 입니다. 

 

문제를 크루스칼 알고리즘으로 풀었습니다.

 

싸이클 없이 트리를 완성 하는 방법

 

싸이클이 생기는 경우

 

싸이클이란 출발한 정점으로 되돌아 오는 경우를 말합니다.

2번 노드 -> 3번 노드 -> 4번 노드 -> 2번 노드

 

싸이클을 어떻게 체크하나요?

크루스칼 알고리즘 에서는 유니온 파인드를 활용 합니다.

 

유니온  파인드

union : 합치다 find : 찾다

시작 노드와 도착 노드의 부모를 확인 하여 ( find ) 다르면 두 정점을 연결 하면 됩니다. ( union )

 

 

부모 배열

 

부모배열 초기값 : 자신 노드번호

 

if( getParent(시작 노드) != getParent(도착 노드)) union( 시작 노드, 부모노드 )
->  둘 중 작은 부모 노드값으로 바꿔 줍니다.

 

 

 

 

크루스칼 알고리즘 순서

 

1. 가중치 기준으로 오름 차순 정렬 합니다.

2. 유니온 파인드를 사용하여 두 노드를 연결 합니다.

 

 

---

 

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class HardToLove14621 {
    static class Node{
        int startNode;
        int endNode;
        int distance;

        public Node(int startNode, int endNode, int distance) {
            this.startNode = startNode;
            this.endNode = endNode;
            this.distance = distance;
        }

        public int getDistance() {
            return distance;
        }
    }

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

    static void unionParent(int[] parent, int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken()); int nodeCount = Integer.parseInt(st.nextToken());

        String[] gender = new String[N+1];
        int[] parent = new int[N+1];
        List<Node> list = new ArrayList<>();

        // 성별 입력 받기
        String[] genderInput = br.readLine().split(" ");
        for(int i = 1; i <= N; i++){
            gender[i] = genderInput[i-1];
        }

        //입력 값 받고 list 넣기
        for(int i = 0; i < nodeCount; i++){
            int[] nodeInput = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int startNode = nodeInput[0]; int endNode = nodeInput[1]; int distance = nodeInput[2];

            list.add(new Node(startNode, endNode, distance));
        }

        // 거리 기준 오름 차순 정렬
        list.sort(Comparator.comparingInt(Node::getDistance));

        for(int i = 1; i <= N; i++){
            parent[i] = i;
        }

        int distanceSum = 0;
        int connectNodeCount = 0;

        for(int i = 0; i < nodeCount; i++){
            Node node = list.get(i);
            int startNode = node.startNode; int endNode = node.endNode;
            boolean equalsGender = gender[startNode].equals(gender[endNode]);

            if(getParent(parent,startNode) != getParent(parent,endNode) && !equalsGender) {
                distanceSum += node.distance;
                unionParent(parent, startNode, endNode);
                connectNodeCount++;
            }

            if(connectNodeCount == N - 1) break;
        }

        if(connectNodeCount == N - 1) System.out.println(distanceSum);
        else System.out.println("-1");
    }
}