[BOJ] 17472. 다리 만들기2 - Prim

[BOJ] 17472. 다리 만들기2 - Prim

제출일 : 2019-10-07

문제 풀이 시간 : 45M

난이도 : ★★★★

Problem

link : https://www.acmicpc.net/problem/17472

Input

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

Output

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

Example

input

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

output

9

Solution & Inpression

문제 풀이 순서

1. 섬을 구분한다

섬의 개수를 파악하하고 그래프를 그리기 위해 섬을 분리하는 작업을 진행한다.

BFS를 이용하여 섬을 라벨링 했다.

2. 그래프를 생성한다.

섬의 개수(정점)의 그래프를 생성한다.

3. 생성된 그래프의 간선을 연결한다.

섬을 잇는 간선을 찾아 연결한다. 이때 다리의 길이는 최소 2이상이어야 한다.

4. 최소신장트리를 이용하여 결과 값을 찾는다.

프림 알고리즘을 이용하여 최소신장트리를 구하고 이때의가중치의 합(결과값)을 찾는다.

모든 정점이 연결되지 못할경우 -1을 리턴한다.

---

삼성 A형 기출문제다 문제가 참 더럽다고 생각한다.

두번째 도전이라 생각보다 시간이 덜 걸렸고 맨처음엔 풀다가 포기했었다.

문제를 풀 순서는 머릿속에 있었지만 간선을 찾지 못했었고, 최소신장트리 알고리즘 또한 아직 익숙지 않았었다.

최소신장트리를 공부하였고 위 문제에 적용하여 해결하였다.

Code

언어 : JAVA

메모리 : 14,396 kb

실행시간 : 108 ms

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N, M, count;
    static int[][] map;
    static int[][] graph;
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    static int[] dist;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int tmp = sc.nextInt();
                if (tmp == 1)
                    map[i][j] = -1;
                else
                    map[i][j] = tmp;
            }
        }
        //1. 섬을 분리한다.
        count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1)
                    BFS(i, j, ++count);
            }
        }
        //2. 그래프를 생성한다.
        graph = new int[count][count];

        for (int i = 0; i < count; i++) {
            for (int j = 0; j < count; j++) {
                if (i == j)
                    continue;
                graph[i][j] = Integer.MAX_VALUE;
            }
        }
        //3. 생성된 그래프의 간선을 연결한다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {

                if (map[i][j] != 0) {
                    for (int dir = 0; dir < 4; dir++) {
                        int r = i + dr[dir];
                        int c = j + dc[dir];
                        if (range(r, c)) {
                            if (map[r][c] == 0) {
                                makeGraph(new int[] { i, j }, new int[] { r, c }, dir, 1);
                            }
                        }
                    }
                }
            }
        }

        dist = new int[count];
        System.out.println(prim(graph));

    }

    public static int prim(int[][] graph) {
        Arrays.fill(dist, -1);
        dist[0] = 0;

        for (int k = 0; k < count; k++) {
            int minWeight = Integer.MAX_VALUE;
            int minVertex = 0;

            for (int i = 0; i < count; i++) {
                if (dist[i] < 0)
                    continue;
                for (int j = 0; j < count; j++) {
                    if (dist[j] >= 0)
                        continue;
                    if (minWeight > graph[i][j]) {
                        minWeight = graph[i][j];
                        minVertex = j;
                    }
                }
            }
            dist[minVertex] = minWeight;

        }
        int sum = 0;
        for (int i = 1; i < count; i++) {
            if(dist[i]==-1)
                return -1;
            sum += dist[i];
        }
        return sum;
    }

    private static void makeGraph(int[] start, int[] cur, int dir, int cnt) {
        int r = cur[0] + dr[dir];
        int c = cur[1] + dc[dir];
        if (range(r, c)) {
            if (map[r][c] == 0) {
                makeGraph(start, new int[] { r, c }, dir, ++cnt);
            } else {
                int s = map[start[0]][start[1]] - 1;
                int e = map[r][c] - 1;
                if (cnt >= 2) {
                    if (graph[s][e] > cnt) {
                        graph[s][e] = cnt;
                        graph[e][s] = cnt;
                    }
                }
            }
        }
    }

    private static void BFS(int i, int j, int cnt) {
        Queue<int[]> q = new LinkedList<int[]>();
        q.offer(new int[] { i, j, cnt });
        map[i][j] = cnt;

        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            for (int k = 0; k < 4; k++) {
                int r = tmp[0] + dr[k];
                int c = tmp[1] + dc[k];
                if (range(r, c)) {
                    if (map[r][c] == -1) {
                        q.offer(new int[] { r, c, cnt });
                        map[r][c] = cnt;
                    }
                }
            }
        }
    }
    private static boolean range(int r, int c) {
        if (0 <= r && r < N && 0 <= c && c < M)
            return true;
        return false;
    }
}