[백준] 17472번 - 다리만들기2 (java)

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	13367	4584	2660	30.272%

입력

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

출력

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

풀이

1. 각 섬을 구분할 수 있도록 번호를 매긴다.
2. 섬이 연결되어 있는지 확인하면서 그에대한 인접행렬을 만든다.
3. 만들어진 인접행렬로 Prim알고리즘을 통해 모든 정점을 연결할 수 있으면 그 값을 출력하고
4. 없으면 -1을 출력한다.

과정

1. 각 섬을 구분하기 위헤 BFS를 수행하며 섬에 번호를 매긴다.

static int classifyIsland() {    
        int count = 1;
        boolean visited[][] = new boolean[N][M];
        Queue<RC> queue = new LinkedList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (map[r][c] == 1 && !visited[r][c]) {
                    queue.offer(new RC(r, c));
                    visited[r][c] = true;

                    while (!queue.isEmpty()) {
                        RC temp = queue.poll();
                        map[temp.r][temp.c] = count;
                        for (int i = 0; i < 4; i++) {
                            int nr = temp.r + deltas[i][0];
                            int nc = temp.c + deltas[i][1];
                            if (isIn(nr, nc) && map[nr][nc] == 1 &&
                                    !visited[nr][nc]) {
                                queue.offer(new RC(nr, nc));
                                visited[nr][nc] = true;
                            }
                        }
                    }
                    count++;
                }
            }
        }
        return count - 1;    // 마지막에 ++를 해줬으므로 -1을 반환
    }

번호를 매긴 후 섬의 갯수를 반환해준다.

2. 각 섬간 연결을 확인하고 최소 거리를 반영해 인접행렬을 만든다.

다리는 가로 또는 세로로만 연결할 수 있으므로

1. 가로 또는 세로로만 확인하며 처음으로 0이아닌 값이 나오면 그 섬의 번호를 start에 저장한다.
2. 섬의 크기를 알 수 없으므로 start != 0 이면서 그 섬을 지나쳤을 때 map[r][c] != start
   3. start가 아닌 섬이 나오면 end에 값을 저장해준다.
   4. end에 값이 저장되면 start,end,count를 이용하여 현재 저장되어있는 값과 비교해 더 작은값을 반영한다.
   5. 섬이 하나의 행 또는 열에 여러개가 있을 수 있으므로( ex. 1 -> 2 -> 3)start를 end로 만들고 end,count를 초기화 후 2번부터 다시 반복한다.
3. 다음 섬까지의 거리를 센다(count++)

static int[][] checkConnected() {    
        int adjMatrix[][] = new int[count + 1][count + 1];
        for (int i = 0; i < count + 1; i++) {
            Arrays.fill(adjMatrix[i], 20000);
        }
        for (int r = 0; r < N; r++) {
            int start = 0, end = 0, count = 0;
            for (int c = 1; c < M; c++) {
                if (map[r][c - 1] != map[r][c]) {
                    if (start == 0 && map[r][c - 1] != 0)
                        start = map[r][c - 1];
                    else if (start != 0)
                        end = map[r][c];
                }
                if (end != 0) {
                    if (count > 1) {
                        adjMatrix[start][end] = 
                            Math.min(adjMatrix[start][end], count);
                        adjMatrix[end][start] = 
                            Math.min(adjMatrix[end][start], count);
                    }
                    start = end;
                    end = 0;
                    count = 0;
                } else if (start != 0 && map[r][c] != start) {
                    count++;
                }

            }
        }
        for (int c = 0; c < M; c++) {
            int start = 0, end = 0, count = 0;
            for (int r = 1; r < N; r++) {
                if (map[r - 1][c] != map[r][c]) {
                    if (start == 0 && map[r - 1][c] != 0)
                        start = map[r - 1][c];
                    else if (start != 0)
                        end = map[r][c];
                }
                if (end != 0) {
                    if (count > 1) {
                        adjMatrix[start][end] = 
                            Math.min(adjMatrix[start][end], count);
                        adjMatrix[end][start] = 
                            Math.min(adjMatrix[end][start], count);
                    }
                    start = end;
                    end = 0;
                    count = 0;
                } else if (start != 0 && map[r][c] != start) {
                    count++;
                }

            }
        }
        return adjMatrix;

    }

3.이후 만들어진 인접행렬에 prim알고리즘을 적용한다.

최종 소스코드

package BJ_Practice;

import java.io.*;
import java.util.*;

public class X_BJ_G2_17472 {
    static int N, M, count;
    static int[][] map;
    static int[][] deltas = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static StringTokenizer st;

    static class RC {
        int r, c;

        public RC(int r, int c) {
            super();
            this.r = r;
            this.c = c;
        }
    }

    static List<Edge> edgeList = new ArrayList<>();

    static class Edge implements Comparable<Edge> {
        int start, end, weight;

        public Edge(int start, int end, int weight) {
            super();
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }

    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        count = classifyIsland();

        int[][] adjMatrix = checkConnected();

        // Prim 알고리즘 시작
        int[] minEdge = new int[count + 1];
        Arrays.fill(minEdge, 20000);
        boolean[] visited = new boolean[count + 1];

        int result = 0; 
        minEdge[1] = 0; 

        for (int i = 1; i <= count; i++) {

            int min = Integer.MAX_VALUE;
            int minVertex = -1;
            for (int j = 1; j <= count; j++) {
                if (!visited[j] && min > minEdge[j]) {
                    min = minEdge[j];
                    minVertex = j;
                }
            }
            visited[minVertex] = true;
            result += min;

            for (int j = 1; j <= count; j++) {
                if (!visited[j] && adjMatrix[minVertex][j] != 0 
                        && minEdge[j] > adjMatrix[minVertex][j]) {
                    minEdge[j] = adjMatrix[minVertex][j];
                }
            }
        }
        if (!(result < 1000 && result > 0))
            result = -1;

        boolean flag = false;
        for (int i = 1; i <= count; i++) {
            if (!visited[i]) {
                flag = false;
                break;
            }
            flag = true;
        }
        if (flag)
            System.out.println(result);
        else System.out.println(-1);

    }

    // 섬 구분하기

    static int classifyIsland() {    
        int count = 1;
        boolean visited[][] = new boolean[N][M];
        Queue<RC> queue = new LinkedList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (map[r][c] == 1 && !visited[r][c]) {
                    queue.offer(new RC(r, c));
                    visited[r][c] = true;

                    while (!queue.isEmpty()) {
                        RC temp = queue.poll();
                        map[temp.r][temp.c] = count;
                        for (int i = 0; i < 4; i++) {
                            int nr = temp.r + deltas[i][0];
                            int nc = temp.c + deltas[i][1];
                            if (isIn(nr, nc) && map[nr][nc] == 1 
                                    && !visited[nr][nc]) {
                                queue.offer(new RC(nr, nc));
                                visited[nr][nc] = true;
                            }
                        }
                    }
                    count++;
                }
            }
        }
        return count - 1;
    }

    // 다리가 연결되어 있다면 인접행렬 만들기.

    static int[][] checkConnected() {    
        int adjMatrix[][] = new int[count + 1][count + 1];
        for (int i = 0; i < count + 1; i++) {
            Arrays.fill(adjMatrix[i], 20000);
        }
        for (int r = 0; r < N; r++) {
            int start = 0, end = 0, count = 0;
            for (int c = 1; c < M; c++) {
                if (map[r][c - 1] != map[r][c]) {
                    if (start == 0 && map[r][c - 1] != 0)
                        start = map[r][c - 1];
                    else if (start != 0)
                        end = map[r][c];
                }
                if (end != 0) {
                    if (count > 1) {
                        adjMatrix[start][end] = 
                            Math.min(adjMatrix[start][end], count);
                        adjMatrix[end][start] = 
                            Math.min(adjMatrix[end][start], count);
                    }
                    start = end;
                    end = 0;
                    count = 0;
                } else if (start != 0 && map[r][c] != start) {
                    count++;
                }
            }
        }
        for (int c = 0; c < M; c++) {
            int start = 0, end = 0, count = 0;
            for (int r = 1; r < N; r++) {
                if (map[r - 1][c] != map[r][c]) {
                    if (start == 0 && map[r - 1][c] != 0)
                        start = map[r - 1][c];
                    else if (start != 0)
                        end = map[r][c];
                }
                if (end != 0) {
                    if (count > 1) {
                        adjMatrix[start][end] = 
                            Math.min(adjMatrix[start][end], count);
                        adjMatrix[end][start] = 
                            Math.min(adjMatrix[end][start], count);
                    }
                    start = end;
                    end = 0;
                    count = 0;
                } else if (start != 0 && map[r][c] != start) {
                    count++;
                }
            }
        }
        return adjMatrix;
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < M;
    }
}