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

[KodaHye]

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

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[jewan100]

🤔 시간복잡도 고려사항

• 섬의 개수 n은 1 이상 100 이하
• costs의 길이는 ((n-1) * n) / 2이하
• MST
  • 프림 알고리즘 → O(E logV)
  • 크루스칼 알고리즘 → O(E logE)
  • 프림이 더 효율적일듯!

💡 풀이 아이디어

• MST를 이루는 간선들의 가중치의 합을 반환
• 프림 알고리즘을 이용해서 MST를 구현
  • 우선 순위 큐를 이용

  PriorityQueue<int[]> pq = new PriorityQueue<int[]>((o1, o2) -> o1[1] - o2[1]); // 가중치 기준 오름차 순
  boolean[] visited = new boolean[n];
  pq.offer(new int[] { 0, 0 });
  int totalWeight = 0;
  while (!pq.isEmpty()) {
      int[] cur = pq.poll();
      if (visited[cur[0]])
          continue;
      visited[cur[0]] = true; // 방문 처리
      totalWeight += cur[1]; // 가중치 누적
      for (int[] edge : edges.get(cur[0]))
          if (!visited[edge[0]]) {
              pq.offer(edge);
          }
  }

간단한 MST문제였군뇨

[KodaHye]

🤔 시간복잡도 고려사항

• 1 ≤ 섬의 개수 ≤ 100
• cost의 길이(주어지는 간선의 개수) ≤ ((n - 1) * n) / 2
• 크루스칼을 통해 MST 구성하기
  • O(ElogE), E: 간선의 개수

💡 풀이 아이디어

최소 비용으로 모든 섬이 서로 통행 가능하도록 만들 때, 최소 비용 구하기 → MST 만들기 (크루스칼 이용)

변수	설명
PriorityQueue<int[]> pq	간선들의 정보 저장 (비용에 대해 오름차순)
int[] p	유니온 파인드를 위해 부모를 저장하는 배열

• int solution(int n, int[][] cost)

PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[2], o2[2]));

// 간선들을 모두 우선순위 큐에 넣어주기
for(int[] cost: costs) pq.add(cost);

p = new int[n + 1];
for(int i = 0; i < p.length; i++) p[i] = i;

int result = 0, cnt = 0;

// 노드가 n개 일 때, 간선은 n - 1개
while(cnt != n - 1) {
    int[] current = pq.poll();
    
    if(find(current[0]) == find(current[1])) continue;
    union(current[0], current[1]);
    
    result += current[2];    
    cnt += 1;
}

• int find(int a): 경로압축 잊지말기!

return p[a] = a == p[a] ? a: find(p[a]);

• void union(int a, int b)

a = find(a);
b = find(b);

if(a != b) p[b] = a;

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ 섬의 개수 ≤ 100 (노드 V)
• costs의 길이 ≤ ((n-1) * n) / 2 (간선 E)
• MST 크루스칼 : O(E logE)

💡 풀이 아이디어

• MST 구하기
  • 가장 적은 비용으로 모든 섬을 연결 == MST
  • MST 알고리즘 → 크루스칼
• 최소 간선을 기준으로 정렬
• 두 정점이 연결되어있지 않다면 연결 및 비용++
  • 두 정점의 연결 여부 확인을 위한 유니온-파인드 연산

public static int solution(int n, int[][] costs) {
        // mst를 위한 간선의 최소비용으로 정렬
        Arrays.sort(costs, ((o1, o2) -> o1[2] - o2[2]));

        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }

        int ans = 0;
        for (int[] c : costs) {
            int p_u = find(c[0]);
            int p_v = find(c[1]);
            if (p_u != p_v) {
                union(p_u, p_v);
                ans += c[2];
            }
        }
        return ans;
    }

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : n<=100, O(N logN) MST 가능

💡 풀이 아이디어

• 섬을 통행 가능하도록 연결할 때 필요한 최소 비용
• MST : 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치 합을 최소로 하는 트리
• 우선순위 큐에 간선 정보 저장 (cost[0], cost[1], cost[2]), (시작, 끝, 가중치)
  • compareTo: 비용에 대해 오름차순으로 정렬해줌
• union-find 초기화
• cnt(추가된 간선 수)를 MST로 최소 비용 간선 선택하며 카운트

- while(!pq.isEmpty() && cnt <n-1){ // 간선 n-1
            Edge edge = pq.poll(); // 최소 비용 간선 선택
            if(find(edge.s) != find(edge.e)){
                union(edge.s, edge.e);
                answer += edge.w;
                cnt++;
            }
        }

⭐ 참고한 것

• MST 우선순위 큐 이용해서 구현, compareTo 부분, 간선수 n-1까지 조건 추가 부분
  • 간선 정보를 쉽게 저장하기 위함, 비용 오름차순 정렬하기 위함, MST시 간선 수 n-1까지

[yeongleej]

🤔 시간복잡도 고려사항

• 섬의 개수 : n <= 100
• 간선의 개수 : ((n-1) * n) / 2

=> MST 가능

• 크루스칼 : O(E log E)
• 프림 : O(E log V)

💡 풀이 아이디어

• 프림 알고리즘 활용
  • 간선을 우선순위 큐에 넣고 비용이 작은 간선부터 연결
  • vistied 배열을 활용해 연결된 노드는 체크

      while(!pq.isEmpty()) {
          Edge now = pq.poll();
          
          if(visited[now.v]) continue;
          visited[now.v] = true;
          answer += now.cost;
          
          // now와 연결된 섬들 탐색
          for(Edge e: g[now.v]) {
              if(visited[e.v]) continue;
              pq.add(e);
          }
      }

이번엔 프림으로 풀어봤습니다~