BJ G3 17472 다리 만들기 2

BJ G3 17472 다리 만들기 2

 

 

문제링크

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

17472번: 다리 만들기 2

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://www.youtube.com/watch?v=Vop0L7vU1-0

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 4. 20.
 * @see https://www.acmicpc.net/problem/17472
 * @mem 13188
 * @time 76
 * @caution #prim, #bfs
 * 1. 섬들을 구별한다.
 * 2. 각 섬을 정점으로 하고 다른 섬과의 거리를 구한다.이때 거리가 1인 경우는 없는 것으로 한다.
 * 3. 각 정점과 섬과의 거리를 이용해 MST 돌린다.
 */
public class BJ_G3_17472_다리만들기2 {
    static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int INF = 987654321;

    static int R, C, islandIdx;
    static int[][] map, graph;

    public static void main(String[] args) throws IOException {
        // 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new StringReader(src));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());

        map = new int[R][C];

        for (int r = 0; r < R; r++) {
            tokens = new StringTokenizer(br.readLine());
            for (int c = 0; c < C; c++) {
                map[r][c] = Integer.parseInt(tokens.nextToken());
            }
        }

        /*        System.out.println("지도 확인");
        for (int[] row : map) {
            System.out.println(Arrays.toString(row));
        }*/


        // 각 섬 구별
        islandIdx = 2;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                // 각 지점을 통해서 BFS. 인덱스를 이용해서 map에 섬의 번호 표현
                if (map[r][c] == 1) {// 미방문의 표시로 1 사용, bfs를 타고 오면 index가 설정될 것
                    bfs(r, c);
                    islandIdx++;
                }
            }
        }
        /*        System.out.println("섬 확인: " + islandIdx);
        for (int[] row : map) {
            System.out.println(Arrays.toString(row));
        }*/

        // graph 구성하기 - 각 섬간에 최단 거리 찾아서 업데이트 - 최대값으로 초기화
        graph = new int[islandIdx][islandIdx];
        for (int r = 2; r < islandIdx; r++) {
            Arrays.fill(graph[r], INF);
        }

        // 각 섬별로 거리 찾아보기
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (map[r][c] > 1) {
                    makeGraph(r, c);
                }
            }
        }

        /*        System.out.println("그래프 확인");
        for (int[] row : graph) {
            System.out.println(Arrays.toString(row));
        }*/

        // MST 구하기
        System.out.println(prim());
    }

    static int prim() {
        // 모든 Vertex들이 여기 들어갈꺼고 다 탈출해야 한다.!!
        PriorityQueue<Vertex> pq = new PriorityQueue<>();

        // 연결 비용과 관련된 섬들의 정보를 관리할 배열
        Vertex[] vertexes = new Vertex[islandIdx];
        for (int i = 2; i < islandIdx; i++) {
            // 그냥 임의의 점에서 시작
            if (i == 2) {
                vertexes[i] = new Vertex(i, 0);
            } else {
                vertexes[i] = new Vertex(i, INF);
            }
            pq.offer(vertexes[i]);
        }

        int sum = 0;
        while (!pq.isEmpty()) {
            Vertex front = pq.poll();

            // 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.
            if (front.cost == INF) {
                return -1;
            }
            sum += front.cost;

            // 가장 가까운 비용으로 업그레이드
            for (int i = 2; i < islandIdx; i++) {
                Vertex child = vertexes[i];
                // 아직 그 정점이 pq에서 관리되고 있다면..
                if (pq.contains(child)) {
                    // 그래프에서 찾아본 비용이 더 작으면 이게 더 유리
                    if (child.cost > graph[front.idx][i]) {
                        child.cost = graph[front.idx][i];
                        // 공간 비용을 절약하기 위해 삭제 후 추가(물론 시간은 더 든다.)
                        pq.remove(child);
                        pq.offer(child);
                    }
                }
            }
        }
        return sum;
    }



    static void makeGraph(int row, int col) {
        int base = map[row][col];
        // 사방으로.. 쭉 가본다.
        for (int d = 0; d < dirs.length; d++) {
            for (int l = 1;; l++) {
                int nr = row + dirs[d][0] * l;
                int nc = col + dirs[d][1] * l;
                if (isIn(nr, nc)) {
                    // 바다면 쭉 건너간다.
                    if (map[nr][nc] == 0) {
                        continue;
                    }
                    // 우리 영역이면 그만
                    else if (map[nr][nc] == base) {
                        break;
                    }
                    // 아니면 다른 섬이다. 근데 거리가 2칸은 떨어져야 하니까 3부터 관심.
                    else {
                        if (l > 2) {
                            // 최소 비용으로 업데이트
                            graph[map[nr][nc]][base] = graph[base][map[nr][nc]] = Math.min(graph[base][map[nr][nc]], l - 1);
                        }
                        break;
                    }
                }
                // 영역에 없으면 그만이야.
                else {
                    break;
                }
            }
        }
    }

    static void bfs(int row, int col) {
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(row, col));

        map[row][col] = islandIdx;

        while (!q.isEmpty()) {
            Pair front = q.poll();

            for (int d = 0; d < dirs.length; d++) {
                int nr = front.row + dirs[d][0];
                int nc = front.col + dirs[d][1];

                if (isIn(nr, nc) && map[nr][nc] == 1) {
                    map[nr][nc] = islandIdx;
                    q.offer(new Pair(nr, nc));
                }
            }
        }
    }

    static boolean isIn(int row, int col) {
        return 0 <= row && row < R && 0 <= col && col < C;
    }

    static class Vertex implements Comparable<Vertex> {
        int idx, cost;

        public Vertex(int idx, int cost) {
            super();
            this.idx = idx;
            this.cost = cost;
        }

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


    }

    static class Pair {
        int row, col;

        public Pair(int row, int col) {
            super();
            this.row = row;
            this.col = col;
        }
    }

    private static String src = "7 8\r\n" +
                                "0 0 0 0 0 0 1 1\r\n" +
                                "1 1 0 0 0 0 1 1\r\n" +
                                "1 1 0 0 0 0 0 0\r\n" +
                                "1 1 0 0 0 1 1 0\r\n" +
                                "0 0 0 0 0 1 1 0\r\n" +
                                "0 0 0 0 0 0 0 0\r\n" +
                                "1 1 1 1 1 1 1 1";
}