[2주차_화요일] 1647_도시 분할 계획

[baexxbin]

• 사이트: 백준
• 문제: 도시 분할 계획
• 번호: 1647번

[yeongleej]

🤔 시간복잡도 고려사항

• N: 집의 게수 <= 100,000
• M: 길의 개수 <=1,000,000 최대 O(M log M) 까지 가능 : 정렬, 다익스트라, 크루스칼 등등 생각해볼 수 있음

💡 풀이 아이디어

• union-find를 활용한 크루스칼 알고리즘 적용

  
  1. 간선을 비용에 따라 오름차순으로 정렬
  2. 간선을 하나씩 확인하며 사이클 발생 여부 확인

• 사이클 발생 O : 최소신장트리에 포함 X
• 사이클 발생 X : 최소신장트리에 포함 O
  3. 두 마을로 나눠야 하기 때문에 가장 마지막에 포함된(가장 큰 비용의 간선)을 제거

[baexxbin]

🤔 시간복잡도 고려사항

• 2 <= N <=100,000, 1<=M <= 1,000,000 → 최대 O(NlogN)
• 그래프 문제로, 유니온파인드, 다익스트라, 크루스칼, bfs등 사용 가능

💡 풀이 아이디어

• 크루스칼(최소 신장트리)이용
  • 문제 조건: 마을 안 길 유지비 최소
  • 크루스칼: 가장 비용이 낮은 간선부터 시작해 간선을 크기 순으로 살펴보며 서로 떨어져 있던 정점들을 합쳐나가서 총 V-1개의 간선을 택하는 알고리즘
• 마을 두개로 분리하기
  • MST구현 후, 가장 큰 비용의 길 삭제하기

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= N <= 100,000, 1 <= M <= 1,000,000
• 다익스트라, MST 등등 그래프 관련 문제 풀이 방법으로 풀이 가능
  • MST 시간 복잡도: MOlog(M)

💡 풀이 아이디어

• 정점(마을)을 최소비용으로 모두 서로 연결되아야 함 → MST
• MST
  • Edge(시작점, 끝점, 비용)를 비용에 대해 우선순위를 적용한 pq에 넣어줌
  • 간선이 (노드의 개수 - 1)개가 될 때까지 간선 이어주기
    • 두 정점의 부모가 같지 않을 때, union연산을 해서 이어주기

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : 2 <= N <= 100,000, 1 <= M <= 1,000,000
• O(N) or O(N log N)
• 두 마을을 분리, 마을 사이의 길의 유지비 합을 최소로
• 크루스칼 알고리즘 : 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 O(E log V)

💡 풀이 아이디어

• MST 사용할 때 사이클이 생기지 않도록 유의
• 모든길을 유지비 기준 오름차순 정렬
• 가장 비용이 큰 간선을 제거해서 두 마을을 분리

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ M ≤ 1,000,000 → 10^6이므로 O(nlogn)

💡 풀이 아이디어

1. 간선의 중복 처리를 위해서 인접 행렬로 구현하려 했지만, 노드의 개수가 최대 100,000이므로 공간 복잡도에서 NG
2. 따라서 우선순위 큐로 가중치 오름차순으로 간선의 정보를 저장
3. Union Find를 이용해서 최소 신장 트리를 구현해줌
   • 경로 압축 및 Union 연산 최적화

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 최소신장트리(MST) > 크루스칼 알고리즘
• 시간복잡도: M은 1이상 1,000,000이하이므로 O(n) 또는 O(NlogN)

💡 풀이 아이디어 최소 신장 트리 알고리즘의 조건을 충족하는 문제

• 같은 마을안에서는 집 사이에 경로가 존재하지만, 길을 없앨 수 있다.
  • 순환 싸이클이 아니더라도 집끼리 연결만 되어 있으면 됨
  • 연결된 경로의 사이는 최소값으로만 연결

추가 요구사항

• 분리된 두 마을 사이에 있는 길들은 없애도 된다
  • 최소 유지비 중 가장 유지비가 큰 값을 제거하기