[SWEA] 1251. 하나로 (with JAVA)

문제 1251

SW Expert Academy

 

[ 접근 과정 ]

문제를 보면, 섬들 간의 거리를 간선의 가중치로 볼 수 있습니다. 가중치 하면 기본적으로 떠오르는 알고리즘이 다익스트라였기에 다익스트라 알고리즘을 이용해서 풀었습니다. 다만, 이전까지 다익스트라 알고리즘 기본 문제들을 풀었을 때는 간선들의 가중치가 주어졌었지만, 이번 문제는 가중치도 직접 구해야 했습니다.

 

[ 고민했던 부분 ]

1. 각 섬들의 위치를 어떻게 저장할 것인가?

각 섬들의 위치를 저장할 때 ArrayList() 를 써야하나 고민했지만, 문제에 나온 x, y 의 범위를 고려했을 때 2차원 배열로 해도 충분할 것이라 생각해서 섬의 개수를 행으로, 열의 크기는 2로 설정하여 각 행마다 x, y 의 위치 2 개의 값을 저장하였습니다.

 

2. 가중치 업데이트를 어떻게 할 것인가?

여기서의 가중치는 두 섬 사이의 거리이고, 이차원 배열로 각 섬의 위치를 저장했으므로 N 만큼 for() 문을 돌아 우선순위 큐에서 가져온 거리와 각 섬들 사이의 거리를 더한 값이 dist[] 에 저장되어 있는 값보다 작으면 우선순위큐에 업데이트된 값을 넣어줍니다.

 

위에서 고민했던 내용들을 바탕으로 아래와 같이 로직을 구현했습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Long.MAX_VALUE;

public class Main {
    private static int N; // 섬의 개수 (정점 개수)
    private static int[][] graph;
    private static boolean[] visit;
    private static long[] dist;
    private static double cost;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            graph = new int[N][2]; // x, y 좌표
            visit = new boolean[N]; // 각 섬의 방문여부
            dist = new long[N];
            cost = 0;
            Arrays.fill(dist, MAX_VALUE);

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i=0; i<N; i++) {
                graph[i][0] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int i=0; i<N; i++) {
                graph[i][1] = Integer.parseInt(st.nextToken());
            }

            double E = Double.parseDouble(br.readLine());

            // 가중치 = 거리
            int start = 0;
            dijkstra(start);

            sb.append("#").append(test_case).append(" ").append(Math.round(cost * E)).append("\n");
        }
        System.out.println(sb);
    }

    private static void dijkstra(int idx) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(idx, 0));

        while (!pq.isEmpty()){
            Node cur = pq.poll();
            int curIdx = cur.idx;
            long curDist = cur.distance;

            if (visit[curIdx]) continue;
            visit[curIdx] = true;
            dist[curIdx] = curDist;
            cost += dist[curIdx];

            for (int i=0; i<N; i++) {
                if (visit[i]) continue;
                long nextDist = (long) (Math.pow(Math.abs(graph[i][0]-graph[curIdx][0]), 2) + Math.pow(Math.abs(graph[i][1]-graph[curIdx][1]), 2));
                if (dist[i] > curDist + nextDist) {
                    pq.offer(new Node(i, nextDist));
                }
            }
        }
    }

    private static class Node implements Comparable<Node> {
        int idx;
        long distance;

        public Node(int idx, long distance) {
            this.idx = idx;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node n) {
            return Long.valueOf(this.distance).compareTo(n.distance);
        }
    }
}

 

---

다익스트라 외에 다른 알고리즘을 활용하여 해결할 수도 있습니다. 이 문제는 얼마나 적은 비용으로 모든 섬을 이을 수 있을 것인가가 핵심입니다. 여기서의 비용은 거리가 됩니다. 즉, 각 섬들을 모두 이었을 때의 거리 합이 최소여야 합니다. 이를 해결하기 위해서 MST (Minimum Spanning Tree) 를 활용할 수 있습니다.

✅  최소 신장 트리(MST) 란?

그래프의 모든 정점을 사이클 없이 잇는 트리에서 간선의 가중치의 합이 최소가 되는 트리

✅  크루스칼 알고리즘이란?

간선 중심으로 최소 신장트리를 구하는 알고리즘으로, 최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘

1. 사이클이 생기지 않아야 함
2. N 개의 정점을 포함하는 그래프에서 N-1 개의 간선을 선택하는 방식

프림 알고리즘은 하나의 트리를 확장시켜 나가는 방식이지만, 크루스칼 알고리즘은 간선을 선택해 나가는 과정에 여러 개의 트리가 존재한다는 차이가 있습니다.

[ 크루스칼 알고리즘 동작 과정 ]
1. 모든 간선을 가중치에 따라 오름차순 정렬
2. 가중치가 낮은 간선부터 선택하면서 트리 증가 (사이클이 존재하면 다음으로 가중치가 낮은 간선 선택)
3. n-1 개의 간선이 선택될 때까지 반복

 

아래는 크루스칼 알고리즘을 사용하는 간단한 문제에 대한 포스트입니다 :)

[SWEA] 4006. 고속도로 건설 2 (with JAVA)