[6주차_금요일] 섬 연결하기

[icegosimperson]

• 사이트 : 프로그래머스(PG)
• 문제: 섬 연결하기
• 번호: 42861

  🤔 시간복잡도 고려사항
  💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 섬의 개수 n은 1 이상 100 이하
• costs의 길이는 ((n-1) * n) / 2이하
• 크루스칼 : O(E logE)
• 프림: O(E logV) → 이게 더 빠를 듯!

💡 풀이 아이디어

• 프림 알고리즘을 이용한 최소 신장 트리 구성

[baexxbin]

🤔 시간복잡도 고려사항

• 1 <= 섬의 개수 n <= 100
• ((n-1) * n) / 2 <= costs의 길이
• 크루스칼 O(ElogE)

💡 풀이 아이디어

• 크루스칼 MST 이용
• 간선과 비용배열 costs가 주어지기에 따로 우선순위 큐는 만들지 않고 리스트 정렬 이용

[yeongleej]

🤔 시간복잡도 고려사항

• 섬의 개수 n <= 100
• costs의 길이(E) <= ((n-1) * n) / 2 => O(ElogE)인 최소신장트리 알고리즘 적용해보기

💡 풀이 아이디어

• 크루스칼 알고리즘 활용
• 2차원 배열을 정렬해서 간선이 가장 작은 edge부터 트리 만들기

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 섬의 개수(노드) <= 100
• 간선의 최대 개수: 100C2 × 2
• 모든 섬이 연결된 경우에서 최소 비용을 구하는 문제이므로 MST로 풀이함
  • 간선의 개수: N일때, 시간복잡도: O(NlogN)

💡 풀이 아이디어

• class Edge
  • int s: 시작점, int e: 끝점, int w: 가중치
• PriorityQueue<Edge> q: cost 배열을 통해 Edge 저장 (Edge.w에 대해 우선순위)
• int mst(): 간선의 노드의 개수 - 1 개 만큼 생길 때 까지 union(), find()하면서 mst 진행

[icegosimperson]

🤔 시간복잡도 고려사항 v=100, O(E logV)

💡 풀이 아이디어

• 최소 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용 구하는 문제
• 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능 -> 모든 섬을 하나의 연결된 그래프로 만들기
• 프림 알고리즘
• Comparable : 비용 기준으로 오름차순 정렬
• PriorityQueue<Point> queue: 최소 비용 간선 선택해서 모든 인접 노드를 확인

MST문제 크루스칼로만 풀어봤었는데, 이번에는 프림으로 한번 풀어 봤습니다ㅎㅅㅎ

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: MST 크루스칼 알고리즘
• 시간복잡도: 섬의 개수 n은 1 이상 100 이하 간선 정렬: O(eloge)

💡 풀이 아이디어

• 문제의 "다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능" == 싸이클이 없는 크루스칼 알고리즘
• 최소 비용 계산을 위해 비용 기준으로 오름차순 정렬 후 union-find 순회
• 최소 신장 트리의 간선수는 n-1 개

처음에는 이미지가 사이클로 형성된 간선이라서 크루스칼이 아닌 DFS 문제라고 생각함