[4주차_화요일] 4386_별자리 만들기

[yeahdy]

• 사이트 : 백준(BOJ)
• 문제: 별자리 만들기
• 번호: 4386

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= n: 별의 개수 <= 100
  • 별을 이을 수 있는 모든 경우의 수(간선): 100C2 = 4950가지
• 모든 별을 이을 수 있는 최소 비용 구하기 → MST
  • 시간복잡도: 4950×Log(4950) < 1억

💡 풀이 아이디어

• Point[] p: 별의 좌표를 배열로 저장
• Edge e: 별의 시작점, 끝점, 비용 저장
  • int s, e; double w;
• Edge의 w에 대해 우선순위큐를 사용해서 MST 구하기
  • 별이 n개 있으므로 간선은 n - 1개까지 이을 수 있음

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 100
• 모든 노드를 탐색해도 상관이 없을 듯
• 프림 알고리즘 O(E logV)

💡 풀이 아이디어

• 최소 신장 트리(MST)의 가중치 합을 구하는 문제
• 모든 별들의 거리를 계산해서 인접 리스트(graph)를 만들음
• 프림 알고리즘으로 구현
• 별과 별 사이의 거리를 최소 힙 우선순위 큐으로 오름차순해서 순회
• 방문하지 않았으면 MST에 추가 및 가중치 합 계산

[yeongleej]

🤔 시간복잡도 고려사항

• n <= 100
• 최대 간선 수(e) : 100C2
• MST 적용 시, e * O(eloge)

💡 풀이 아이디어

• 크루스칼 알고리즘으로 별들 사이의 간선을 모두 구한 후 계산
• parent[] : 별들의 부모 인덱스 배열
• eList : 간선 리스트
• 우선순위 큐를 활용하여 간선의 길이가 작은 순서대로 별자리 만들기(MST) 진행
• 실수 compareTo()
  • Comparable을 상속받을 때, 실수 비교는 Double.compare() 활용

[baexxbin]

🤔 시간복잡도 고려사항

• n <= 100
• 최대 간선 수 : 100C2 → 4950
• 크루스칼 O(ElogE)
• O(ElogE)*간선 수

💡 풀이 아이디어

• 크루스칼 MST 이용

  • 크루스칼은 간선을 기준으로 하기에, 별자리 좌표를 통해 간선 만듦
  • 해당 (간선,노드u, 노드v) 우선순위 큐에 넣음
  • 이때 노드는 별자리 점 dots의 인덱스

• 크루스칼, 유니온파인드 진행

크루스칼 파바박 풀리도록 더 연습하기!

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 최소 신장 트리(MST) > union-find
• 시간복잡도: 1 ≤ n ≤ 100
  • 간선 정렬: O(eloge)
  • MST 경로압축: O(a(N))
  • O(eloge) + O(a(N)) = O(eloge)

💡 풀이 아이디어

서로 다른 두 별을 일직선으로 이은 형태, 별자리를 만드는 최소 비용

• 순환하지 않는 연결된 그래프 형태로 최소 값을 구하는 최소 신장 트리 문제
• {x,y} 좌표 하나를 노드로 생각 (행 단위로 노드)
• 두 별 사이의 거리 구하는 방법?
  • 두 점 x좌표와 y좌표 각각의 차이
  • x좌표,y좌표 차이 제곱
  • 두 제곱의 합 제곱급

[icegosimperson]

🤔 시간복잡도 고려사항

• 1 <= n <= 100, 모든 간선 조사 가능
• 최소 신장트리 (MST) -> 크루스칼 알고리즘 이용

💡 풀이 아이디어

• 각 별 쌍에 거리를 계산한 후, (거리, 별1, 별2) 형태의 간선 리스트 생성
• 간선 오름차선으로 정렬
• 크루스칼 알고리즘(Union-find)을 사용하여 MST를 구성
• 두 별 사이의 거리 공식