[BOJ] 백준 1774. 우주신과의 교감

2024. 6. 24. 20:32· Java/BOJ

문제

https://www.acmicpc.net/problem/1774

 


풀이

크루스칼을 이용해 MST를 구하는 문제입니다. 백준의 4386번. 별자리 만들기 문제와 상당히 비슷합니다.

 

 이 문제의 핵심은 좌표(x, y)를 하나의 인덱스로 다루는 것이라고 생각합니다. 좌표를 입력받고, 좌표들을 간선으로 연결할 때에 인덱스를 매겨주며 ArrayList에 추가하고, 간선에 추가된 좌표의 위치는 거리를 구하기 위해서 필요할 뿐이지 더는 필요가 없으므로 시작과 종료 지점의 인덱스로 변환하고 좌표는 버립니다.

 

 그리고 크루스칼 알고리즘을 인덱스로 실행하며 union시에 통로 길이 합을 더해주었습니다.

 

 아래는 소스 코드입니다.


소스 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class B1774_우주신과의교감 {

    static Scanner sc = new Scanner(System.in);
    static int N,M;
    static int[] parents;
    static ArrayList<int[]> list = new ArrayList<>();
    static ArrayList<Node> edgeList = new ArrayList<>();
    static double ans = 0;

    static class Node implements Comparable<Node>{
        int st;
        int ed;
        double w;

        Node(int st, int ed, double w){
            this.st=st;
            this.ed=ed;
            this.w=w;
        }

        @Override
        public int compareTo(Node o){
            return Double.compare(w, o.w);
        }
    }

    public static void main(String[] args) {
        input();
        connect();
        kruskal();
        System.out.printf("%.2f", ans);
    }

    static void kruskal(){
        for(int i = 0; i<edgeList.size();i++){
            int st = edgeList.get(i).st;
            int ed = edgeList.get(i).ed;
            double w = edgeList.get(i).w;
            if(!isParent(st,ed)){
                union(st,ed);
                ans += w;
            }
        }
    }

    static void connect(){
        for(int i =0; i<N-1;i++){
            for(int j = i+1;j<N;j++){
                int[] o1 = list.get(i);
                int[] o2 = list.get(j);
                edgeList.add(new Node(i,j,getDistance(o1,o2)));
            }
        }
        Collections.sort(edgeList);
    }

    static void input(){
        N = sc.nextInt();
        M = sc.nextInt();
        parents = new int[N+1];
        for(int i = 0; i<N+1;i++) parents[i] = i;

        for(int i =0; i<N;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            list.add(new int[]{x,y});
        }
        for(int i = 0; i<M;i++){
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            union(a,b);
        }
    }

    static int findset(int a){
        if(parents[a]!=a) return parents[a]=findset(parents[a]);
        return a;
    }
    static void union(int a, int b){
        a = findset(a);
        b = findset(b);
        if(a!=b){
            parents[b] = a;
        }
    }
    static boolean isParent(int a, int b){
        if(findset(a)!= findset(b)) return false;
        return true;
    }
    static double getDistance(int[] o1, int[] o2){
        int r1 = o1[0];
        int c1 = o1[1];
        int r2 = o2[0];
        int c2 = o2[1];
        return Math.sqrt(Math.pow(r1-r2,2)+Math.pow(c1-c2,2));
    }
}

'Java > BOJ' 카테고리의 다른 글

[BOJ] 백준 25192. 인사성 밝은 곰곰이  (0) 2024.07.21
[BOJ] 백준 14658. 하늘에서 별똥별이 빗발친다  (0) 2024.06.30
[BOJ] 백준 20310. 타노스  (0) 2024.06.21
[BOJ] 백준 1138. 한 줄로 서기  (0) 2024.06.10
[BOJ] 백준 17266. 어두운 굴다리  (0) 2024.05.31
'Java/BOJ' 카테고리의 다른 글
  • [BOJ] 백준 25192. 인사성 밝은 곰곰이
  • [BOJ] 백준 14658. 하늘에서 별똥별이 빗발친다
  • [BOJ] 백준 20310. 타노스
  • [BOJ] 백준 1138. 한 줄로 서기
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (177)
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (32)
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (5)
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 자바
  • 한양대
  • Java
  • 김영한
  • 스택
  • 네트워크
  • 프로그래머스
  • 이석복
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 구현
  • 큐
  • 반효경
  • BOJ
  • JCF
  • 레디스
  • 자바스크립트
  • 인프런
  • 백준
  • 운영체제
  • OS

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[BOJ] 백준 1774. 우주신과의 교감
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.