[SWEA/Java] 1251. [S/W 문제해결 응용] 4일차 - 하나로

🔗 문제 링크

삼성 SW Expert Academy - 트리 | 1251. [S/W 문제해결 응용] 4일차 - 하나로

SW Expert Academy

 

ps. 이번 문제는 해당 사이트에 가입해야 문제를 볼 수 있습니다 🥲

---

✔️ 소요된 시간

3시간

---

✨ 수도 코드

이 문제는 Minimum Spanning Tree를 구하는 문제였습니다

✅ Minimum Spanning Tree란?

그래프에서 간선의 수를 가장 적게, 즉 n개의 정점을 가지는 그래프에서 n-1개의 간선을 선택해서 만든 트리가 Spanning Tree입니다
그리고 이때 간선의 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것이 MST(Minimum Spanning Tree)입니다

⭐️ 링크를 참고하면 이해에 도움이 될 것 같습니다!

 

이 문제에서는 섬이 노드이고, 해저터널이 간선, 환경부담금이 가중치라고 생각할 수 있습니다. 모든 섬 사이가 간선으로 연결되어있는 그래프가 있다고 생각하고, 해당 그래프에서 n-1의 간선을 선택하여 MST를 만들면 최소한의 환경부담금으로 모든 섬을 해저터널로 연결이 가능합니다!

환경부담금은 (해저터널로 연결하는 섬 사이의 거리)^2 * E(환경 부담 세율)인데, 저는 계산을 최소화하기 위해서 (해저터널로 연결하는 섬 사이의 거리)^2를 가중치로 설정하고, 최종 누적 가중치에 E(환경 부담 세율)를 곱해주었습니다

private static class Edge implements Comparable<Edge> {
    int island1, island2;
    Long cost; // 비용 = 환경 부담금 (* E는 마지막에)

    Edge(int island1, int island2, Long cost) {
      this.island1 = island1;
      this.island2 = island2;
      this.cost = cost;
    }
}

ArrayList<Edge> edges = new ArrayList<>();
for(int i = 0; i < N; i++) {
  for(int j = i + 1; j < N; j++) {
    Long distanceX = island[i][0] - island[j][0];
    Long distanceY = island[i][1] - island[j][1];
    Long cost = (distanceX * distanceX) + (distanceY * distanceY);

    edges.add(new Edge(i, j, cost));
  }
}

 

간선(해저터널)로 연결된 노드(섬)과 가중치를 저장하는 class Edge를 정의해두고, 모든 간선에 대해 가중치를 구해서 ArrayList에 넣어주었습니다

이때, 가중치를 최소로 해야하므로 해당 데이터를 가중치 기준으로 오름차순 정렬하고, 작은 것부터 선택을 하는 방법을 적용할 수 있습니다!

// 환경부담금 기준 오름차순 정렬
@Override
public int compareTo(Edge edge) {
  if(edge.cost < cost) return 1;
  else if(edge.cost > cost) return -1;
  return 0;
}

// 환경부담금 순으로 오름차순 정렬
Collections.sort(edges);

 

가중치가 적은 간선부터 선택을 하는데, 주의해야 하는 부분은 cycle이 생기지 않도록 하는 것입니다. 이미 두 노드 사이가 연결되어있는데 또 연결을 해서 cycle을 만들면 더이상 최소라고 볼 수 없기 때문입니다!

cycle이 생길 수 있는지, 즉 이미 두 섬 사이가 연결되어 있는지 확인하기 위해서 각 노드의 root 노드를 찾고 비교하는 작업을 해주었습니다. 사이클이 없게 하려면 트리 형태로 구성할 수 있기 때문에 부모 노드를 찾을 수 있습니다. 이어진 섬 중 어느쪽을 부모로 하고, 어느쪽을 자식으로 하는지는 상관 없이 풀이가 가능합니다

간선을 선택할 때마다 노드 사이가 연결되어있는지 체크하고, 연결되어 있지 않다면 해당 간선을 선택해줍니다. 그리고 N-1개의 간선이 선택되어 MST가 완성되었다면 누적가중치에 E를 곱한 뒤 반올림해주면 됩니다!!

🔥 최종 코드

// 5차시 2024.07.31.수 : SW Expert Academy - 1251. [S/W 문제해결 응용] 4일차 - 하나로
package jung0115.트리;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.lang.Math;


public class SWEA_1251 {
  static Long[][] island;
  static int[] parents;
  private static class Edge implements Comparable<Edge> {
    int island1, island2;
    Long cost; // 비용 = 환경 부담금 (* E는 마지막에)

    Edge(int island1, int island2, Long cost) {
      this.island1 = island1;
      this.island2 = island2;
      this.cost = cost;
    }

    // 환경부담금 기준 오름차순 정렬
    @Override
    public int compareTo(Edge edge) {
      if(edge.cost < cost) return 1;
      else if(edge.cost > cost) return -1;
      return 0;
    }
  }

	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder printSet = new StringBuilder();

		int T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++)
		{
      int N = Integer.parseInt(br.readLine()); // 섬의 개수
      island = new Long[N][2];

      // X 좌표
      StringTokenizer st = new StringTokenizer(br.readLine());
      for(int i = 0; i < N; i++) {
        island[i][0] = Long.parseLong(st.nextToken());
      }

      // Y 좌표
      st = new StringTokenizer(br.readLine());
      for(int i = 0; i < N; i++) {
        island[i][1] = Long.parseLong(st.nextToken());
      }

      Double E = Double.parseDouble(br.readLine()); // 환경 부담 세율

      // 각 섬을 잇는 해저터널의 환경 부담금 (* E는 마지막에)
      ArrayList<Edge> edges = new ArrayList<>();
      for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
          Long distanceX = island[i][0] - island[j][0];
          Long distanceY = island[i][1] - island[j][1];
          Long cost = (distanceX * distanceX) + (distanceY * distanceY);

          edges.add(new Edge(i, j, cost));
        }
      }

      // 환경부담금 순으로 오름차순 정렬
      Collections.sort(edges);

      // root 노드를 자기 자신으로 초기화
      parents = new int[N];
      for(int i = 0; i < N; i++) {
        parents[i] = i;
      }

      int connect = 0; // 연결된 섬의 개수
      Long totalCost = 0L; // 총 환경부담금
      for(Edge edge : edges) {
        if(isConnect(edge.island1, edge.island2)) continue;
        
        totalCost += edge.cost;
        connect++;
        if(connect == N - 1) break;
      }

      Long answer = Math.round(E * totalCost);
      printSet.append("#").append(test_case).append(" ").append(answer).append("\n");
    }

    br.close();
    System.out.print(printSet);
	}

  // 연결되어있는지 체크
  static private boolean isConnect(int island1, int island2) {
    int root1 = findRoot(island1);
    int root2 = findRoot(island2);

    if(root1 == root2) return true; // root 노드가 같다면, 이미 연결되어 있는 것
    parents[root1] = root2;
    return false;
  }

  // root 노드 찾기
  static private int findRoot(int node) {
    if(node == parents[node]) return node;
    
    parents[node] = findRoot(parents[node]);
    return parents[node];
  }
}

---

📚 새롭게 알게된 내용

처음에는 해저터널이 서로 양방향 연결이 되어있으니까 당연히 그래프로 풀어야겠다고 생각했는데, 가중치를 최소로 하려면 cycle이 생기면 안 된다는 포인트를 발견하고 트리처럼 풀이하게된 것 같습니다!

 

5-jung0115 by jung0115 · Pull Request #137 · AlgoLeadMe/AlgoLeadMe-4