[백준] 14621 나만 안되는 연애 JAVA

김영훈·2022년 5월 12일
0

알고리즘

목록 보기
9/9

문제

깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.

이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.

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

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

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

입력

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000)

둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다.

다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)

출력

깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)

문제 풀이

  • 모든 경로를 만든 것을 구하는 최소 스패닝 트리를 구하는 문제라고 생각했다
  • MST를 구현하는 알고리즘 중 크루스칼 알고리즘을 사용해서 문제를 해결하자고 생각했다.
  1. 먼저 주어진 입력값을 받는다
  2. 조건중 동일한 성별이면 LIst에 처음부터 넣지 않는다
int u, v, d;
for (int i = 0; i < M; i++) {
    in = br.readLine().split(" ");
    u = Integer.parseInt(in[0]);
    v = Integer.parseInt(in[1]);
    d = Integer.parseInt(in[2]);

    // 동일한 성별이면 리스트에서 제외한다
    if (arr[u] == arr[v]) continue;

    edgeList.add(new Edge(u, v, d));
}
  1. 가중치 크기 순으로 정렬한다
Collections.sort(edgeList, (o1, o2) -> Integer.compare(o1.d, o2.d));
  1. 부모를 초기화하고 N-1 까지 연결되면 답을 출력한다
initParents();

int nodeCnt = 0;
int answer = 0;
for (Edge temp : edgeList) {

    if (union(temp.u, temp.v)) {
        nodeCnt++;
        answer += temp.d;
        if (nodeCnt == N - 1) {
            System.out.println(answer);
            return;
        }
    }
}

System.out.println(-1);

풀이 코드

package BOJ;

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

public class BOJ_나만안되는연애_HoonyCode {

    static int N, M;
    static char[] arr;
    static int[] parents;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        // 학교의 수 N 과 도로의 개수 M;
        String[] in = br.readLine().split(" ");
        N = Integer.parseInt(in[0]);
        M = Integer.parseInt(in[1]);
        parents = new int[N + 1];

        arr = new char[N + 1];
        in = br.readLine().split(" ");
        // 남 녀 구별 M // W;
        for (int i = 1; i <= N; i++) {
            arr[i] = in[i - 1].charAt(0);
        }

        List<Edge> edgeList = new ArrayList<>();

        int u, v, d;
        for (int i = 0; i < M; i++) {
            in = br.readLine().split(" ");
            u = Integer.parseInt(in[0]);
            v = Integer.parseInt(in[1]);
            d = Integer.parseInt(in[2]);

            if (arr[u] == arr[v]) continue;

            edgeList.add(new Edge(u, v, d));
        }

        Collections.sort(edgeList, (o1, o2) -> Integer.compare(o1.d, o2.d));

        initParents();

        int nodeCnt = 0;
        int answer = 0;
        for (Edge temp : edgeList) {

            if (union(temp.u, temp.v)) {
                nodeCnt++;
                answer += temp.d;
                if (nodeCnt == N - 1) {
                    System.out.println(answer);
                    return;
                }
            }
        }

        System.out.println(-1);
    }

    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return false;
        } else {
            parents[y] = x;
            return true;
        }
    }

    static void initParents() {
        for (int i = 1; i <= N; i++) {
            parents[i] = i;
        }
    }

    static int find(int x) {

        if (x != parents[x]) {
            return parents[x] = find(parents[x]);
        }
        return parents[x];
    }

    static class Edge {
        int u, v, d;

        public Edge(int u, int v, int d) {
            this.u = u;
            this.v = v;
            this.d = d;
        }
    }

}
profile
배우는 개발자가 되고 싶습니다.

0개의 댓글