정범의 프로그래밍 블로그 입니다.

4 분 소요

1. 핵심 개념 및 근거

필요한 개념 및 자료구조

  • Prim 알고리즘: 하나의 시작 정점에서부터 연결된 정점들 중 가장 가중치가 작은 간선을 선택하며 트리를 확장해 나가는 그리디 기반 MST 알고리즘입니다.

  • 우선순위 큐 (PriorityQueue): 현재 연결된 정점 집합에서 연결되지 않은 정점으로 가는 간선들 중 최솟값을 빠르게 찾기 위해 사용합니다.

  • 방문 배열 (Visited): 이미 MST에 포함된 정점을 다시 선택하지 않도록 관리합니다.

선택 근거 및 제약사항

  • 밀집 그래프의 특성: 이 문제는 모든 섬이 서로 연결될 수 있는 완전 그래프입니다. 간선의 개수 E가 약 50만 개로 많기 때문에, 정점 중심인 Prim 알고리즘이 효율적입니다.
  • 동적 확장: Kruskal은 모든 간선을 미리 만들고 정렬해야 하지만, Prim은 현재 정점에서 갈 수 있는 곳만 탐색하므로 메모리 관리 측면에서 직관적입니다.
  • 시간 복잡도: 우선순위 큐를 이용하면 O(ElogV) 방식을 사용하면 범용적으로 사용합니다.


2. 추론 과정

  1. “모든 섬을 연결해야 한다”: 그래프 내 모든 정점을 잇는 ‘연결 그래프’를 만들어야 함을 인지합니다.
  2. “환경 부담금의 합을 최소화”: 간선 가중치의 총합을 최소로 만드는 ‘최소 신장 트리’ 문제임을 확신합니다.
  3. “좌표 기반 거리”: 간선의 가중치가 고정된 값이 아니라 두 점 사이의 거리로 정의되어 있으므로, 탐색 과정에서 실시간으로 계산하거나 미리 계산해둘 수 있음을 파악합니다.


3. 설계 및 접근

  1. 정점 및 간선 구조 설계: 섬의 번호와 해당 섬까지의 최소 비용을 저장할 Node 클래스를 설계합니다.
  2. 임의의 시작점 설정: 보통 0번 섬을 시작점으로 잡고 우선순위 큐에 넣습니다.
  3. 반복 탐색 (MST 확장):
    • 큐에서 가장 비용이 적은 Node를 꺼냅니다.
    • 해당 섬이 이미 방문되었다면 무시합니다.
    • 방문되지 않았다면 해당 비용을 누적하고 방문 처리합니다.
    • 방금 방문한 섬에서 아직 방문하지 않은 다른 모든 섬까지 거리를 계산하여 큐에 삽입합니다.
  4. 종료 조건: 연결된 정점의 개수가 $N$개가 되면 반복을 멈춥니다.
  5. 최종 계산: 누적된 합계에 세율 E를 곱하고 반올림합니다.


4. 예시 시뮬레이션

상황: 섬 A(0,0), B(3,0), C(0,4), E = 0.1

  1. 시작 (A): 큐에 (A, 비용 0) 삽입. 방문 배열 [F, F, F]
  2. 1회전: 큐에서 A 추출. 방문 처리 [T, F, F].
    • A에서 갈 수 있는 B(비용 9), C(비용 16)를 큐에 삽입.
  3. 2회전: 큐에서 가장 저렴한 B(비용 9) 추출. 방문 처리 [T, T, F].
    • B에서 갈 수 있는 C(비용 25)를 큐에 삽입. (현재 큐: [C(16), C(25)])
  4. 3회전: 큐에서 가장 저렴한 C(16) 추출. 방문 처리 [T, T, T].
    • 모든 정점 방문 완료.
  5. 결과: 0(A) + 9(B) + 16(C) = 25.
    • 최종 25 X 0.1 = 2.5 -> 반올림 3.


5. 주의 사항

  • 메모리 관리:
    • 모든 간선을 미리 ArrayList에 담아두면 메모리 사용량이 늘어날 수 있습니다.
    • 프림에서는 큐에 넣을 때 실시간으로 거리를 계산하는 방식이 메모리 효율적입니다.
  • 자료형 오버플로우: 크루스칼과 마찬가지로 거리의 제곱을 합산할 때 반드시 long 타입을 사용해야 합니다.
  • 실수 연산: E는 소수점이므로 마지막 계산 단계 전까지는 정수형(long)으로 유지하여 오차를 방지해야 합니다.


6. 코드 풀이

6.1 정점 및 간선 구조 설계

static class Node implements Comparable<Node> {
	int to;
	long weight;

	public Node(int to, long weight) {
		super();
		this.to = to;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		// TODO Auto-generated method stub
		return Long.compare(this.weight, o.weight);
	}
}
  • 섬의 번호와 해당 섬까지의 최소 비용을 저장할 Node 클래스를 설계합니다.

6.2 프림 알고리즘

6.2.1 임의의 시작점 설정

pq.add(new Node(0, 0));
  • 보통 0번 섬을 시작점으로 잡고 우선순위 큐에 넣습니다.

6.2.2 반복 탐색(MST 확장)

while (!pq.isEmpty()) {
    Node cur = pq.poll();
    int cur_to = cur.to;
    long cur_w = cur.weight;
 
    // 이미 방문한 곳은 다음으로 넘어간다.
    if (visited[cur_to])
        continue;
 
    // 방문 처리 및 비용 누적
    visited[cur_to] = true;
    result += cur_w;
                 
    // 모든 섬을 연결하면 종료
    if(++count == N)
        break;
 
    for (int next = 0; next < N; next++) {
 
        // 이미 방문한 정점은 다음으로 넘어간다.
        if (visited[next])
            continue;
 
        // 거리 계산
        long diffx = xlist[cur_to] - xlist[next];
        long diffy = ylist[cur_to] - ylist[next];
        long dist = diffx * diffx + diffy * diffy;
 
        pq.add(new Node(next, dist));
    } 
}
  • 큐에서 가장 비용이 적은 Node를 꺼냅니다.
  • 해당 섬이 이미 방문되었다면 무시합니다.
  • 방문되지 않았다면 해당 비용을 누적하고 방문 처리합니다.
  • 모든 섬을 연결했다면 종료합니다.
  • 방금 방문한 섬에서 아직 방문하지 않은 다른 모든 섬까지 거리를 계산하여 큐에 삽입합니다.

6. 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        // T 입력
        int T = Integer.parseInt(br.readLine().trim());
 
        // tc 수행
        for (int tc = 1; tc <= T; tc++) {
 
            StringTokenizer st = null;
 
            // 섬의 개수 입력
            int N = Integer.parseInt(br.readLine());
 
            // 초기화
            int[] xlist = new int[N];
            int[] ylist = new int[N];
 
            // x좌표 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                xlist[i] = Integer.parseInt(st.nextToken());
            }
 
            // y좌표 입력
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                ylist[i] = Integer.parseInt(st.nextToken());
            }
 
            // 환경 부담 세율 실
            double E = Double.parseDouble(br.readLine());
 
            // 방문 체크 배열
            boolean visited[] = new boolean[N];
 
            // 프림에 사용할 큐
            PriorityQueue<Node> pq = new PriorityQueue<>();
 
            // 시작점 입력
            pq.add(new Node(0, 0));
 
            long result = 0; // MST 비용
            int count = 0; // 섬의 연결 횟수
 
            // 방문할 곳이 없을 때까지 수행
            while (!pq.isEmpty()) {
 
                Node cur = pq.poll();
                int cur_to = cur.to;
                long cur_w = cur.weight;
 
                // 이미 방문한 곳은 다음으로 넘어간다.
                if (visited[cur_to])
                    continue;
 
                visited[cur_to] = true;
                result += cur_w;
                 
                if(++count == N)
                    break;
 
                for (int next = 0; next < N; next++) {
 
                    // 이미 방문한 정점은 다음으로 넘어간다.
                    if (visited[next])
                        continue;
 
                    // 거리 계산
                    long diffx = xlist[cur_to] - xlist[next];
                    long diffy = ylist[cur_to] - ylist[next];
                    long dist = diffx * diffx + diffy * diffy;
 
                    pq.add(new Node(next, dist));
                }
 
            }
 
            // 출력 내용 추가
            sb.append("#" + tc + " " + Math.round(E * result) + "\n");
 
        } // tc 종료
 
        // 출력
        System.out.println(sb);
 
    } // 메인 종료
 
    // Node 클래스
    static class Node implements Comparable<Node> {
        int to;
        long weight;
 
        public Node(int to, long weight) {
            super();
            this.to = to;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            // TODO Auto-generated method stub
            return Long.compare(this.weight, o.weight);
        }
    }
 
}

카테고리:

업데이트:

참고

창용 마을 무리의 개수

3 분 소요

1. 문제 접근 방법 및 아이디어 이 문제는 여러 명의 사람이 있고, 그들 사이의 관계가 주어질 때, 총 몇 개의 독립된 그룹이 형성되는가?를 구합니다.

서로소 집합

3 분 소요

1. 문제 접근 방법 및 아이디어 이 문제는 여러 개의 원소가 있을 때, 이들을 합치거나 같은 그룹에 속해 있는지 확인하는 과정을 효율적으로 처리하는 것이 핵심입니다. 독립된 원소 생성 처음에는 모든 숫자가 각각 자기 자신만을 원소로 갖는 집합이 됩니다. ...