[백준 17472] 다리만들기2

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

17472번: 다리 만들기 2

 

 

문제 접근 방법

1. 입력받기 : 입력을 받아서 2차원 배열에 지도 정보 저장

 

2. 섬의 개수 카운팅  & 섬 리스트에 저장 & 섬 구별 라벨링

섬 : 1이 뭉쳐있는 곳 -> dfs, bfs 로 찾기

섬 리스트에 저장 : Island 클래스를 만들어서 Point 객체 리스트를 변수로 넣어줌

섬 구별 라벨링 : dfs를 돌면서 섬마다 1부터 라벨링(인덱싱)을 해줌

 

3. 섬 간의 관계(거리)를 계산해서 dist 2차월 배열에 거리 저장

dist 2차원 배열에 Integer.MAX_VALUE를 채워준다 ( 최솟값 갱신을 위해서 )

섬 리스트를 순회하며 가로 방향에 있는 섬, 세로 방향에 있는 섬을 나누어 계산 : dist[i][j] 에 넣어주고 계속해서 최솟값 갱신

 

단, 여기서 주의할 점 

 

난 위의 경우에 있는 1번, 3번 섬 사이의 거리를 구할 때 (0, 4) - (4, 4) 사이의 거리를 자꾸만 구해버려서 동일한 섬 안에 공간이 있는 경우를 구별했다.

 

4. 섬이 연결되어 있는지 확인 : 플로이드-워샬 알고리즘 -> 연결되어 있지 않으면 -1 바로 출력

 

5. 섬이 연결되어 있다면 간선의 값이 최소인 리스트 구성 : 크루스칼 알고리즘

 

 

 

 

### 코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Main {
    static int N, M, index = 1, INF = 1000000;
    static int[] parent;
    static int[][] map, dir={{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, dist;
    static boolean[][] visited;
    static List<Island> islands;
    static List<Edge> edgeList;

	// 섬 정보 클래스 
    static class Island{
        int idx;
        List<Point> list;
        public Island(int idx){
            this.idx = idx;
            list = new ArrayList<>();
        }
    }

	// 간선리스트 클래스 
    static class Edge implements Comparable<Edge> {
        int from, to, weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        public int compareTo(Edge o){
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) throws IOException {
        // 1. 입력받기
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.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(in.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 2. 섬 갯수 카운팅 & 배열에 저장 & 섬 구별해주기
        visited = new boolean[N][M];
        islands = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Island island = new Island(index);
                if(map[i][j] == 1 && !visited[i][j] && splitIsland(i, j, island)) {
                    islands.add(island);
                    index++;
                }
            }
        }
        index -= 1;

        // 3. 섬 간의 관계(거리)를 계산
        dist = new int[index][index];
        for (int i = 0; i < index; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        // 1~N 개의 섬 순회
        for(Island island: islands){
            // 섬들 지점 순회하면서 다른 섬을 만날때까지 도달해서 거리 구하기
            dist[island.idx - 1][island.idx - 1] = 0;

            for(Point p: island.list){
                int x = p.x;
                int y = p.y;

                // 가로 방향 (0, 1) 계속 증가
                int d = 0;
                int incrementIdx = 0;
                boolean flag = false;
                while(true){
                    int dy = y + ++incrementIdx;
                    if(dy >= M) break;
                    if(flag && map[x][dy] == map[x][y]) break;
                    if(map[x][dy] != 0 && map[x][dy] != map[x][y]) {
                        if(d >= 2) dist[island.idx - 1][map[x][dy] - 1] = Math.min(d, dist[island.idx - 1][map[x][dy] - 1]);
                        break;
                    } else if(map[x][dy] == 0) {
                        d++;
                        flag = true;
                    }
                }

                // 세로 방향 (1, 0) 계속 증가
                d = 0;
                flag = false;
                incrementIdx = 0;
                while(true){
                    int dx = x + ++incrementIdx;
                    if(dx >= N) break;
                    if(flag && map[dx][y] == map[x][y]) break;
                    if(map[dx][y] != 0 && map[dx][y] != map[x][y]) {
                        if(d >= 2) {
                            dist[island.idx - 1][map[dx][y] - 1] = Math.min(d, dist[island.idx - 1][map[dx][y] - 1]);
                        }
                        break;
                    } else if(map[dx][y] == 0) {
                        d++;
                        flag = true;
                    }
                }
            }
        }

        edgeList = new ArrayList<>();
        for (int i = 0; i < index; i++) {
            for (int j = 0; j < index; j++) {
                if(dist[i][j] != Integer.MAX_VALUE) dist[j][i] = dist[i][j];
                else dist[i][j] = INF;
                if(dist[i][j] != 0) edgeList.add(new Edge(i, j, dist[i][j]));
            }
        }

        // 4. 섬이 연결되어 있는지 확인
        for (int k = 0; k < index; k++) {
            for (int i = 0; i < index; i++) {
                for (int j = 0; j < index; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for (int i = 0; i < index; i++) {
            for (int j = 0; j < index; j++) {
                if(dist[i][j] == INF){
                    System.out.println(-1);
                    System.exit(0);
                }
            }
        }

        // 5. 간선의 값이 최소인 리스트 구성하기
        parent = new int[index + 1];
        for (int i = 0; i < index + 1; i++) {
            parent[i] = i;
        }

        Collections.sort(edgeList);
        int ans = 0;
        int cnt = 0;
        for(Edge e: edgeList){
            if(union(e.from, e.to)){
                ans += e.weight;
                if(++cnt == islands.size() - 1) break;
            }
        }

        System.out.println(ans);
    }

    private static boolean splitIsland(int r, int c, Island island) {
        if(r < 0 || r >= N || c < 0 || c >= M || visited[r][c]) return false;
        if(map[r][c] == 0) return false;

        visited[r][c] = true;
        island.list.add(new Point(r, c));
        map[r][c] = index;

        for (int i = 0; i < 4; i++) {
            int dr = r + dir[i][0];
            int dc = c + dir[i][1];

            splitIsland(dr, dc, island);
        }
        return true;
    }

    private static boolean union(int from, int to){
        int fRoot = find(from);
        int tRoot = find(to);

        if(fRoot == tRoot) return false;

        parent[fRoot] = tRoot;
        return true;
    }

    private static int find(int v){
        if(parent[v] == v) return v;
        return parent[v] = find(parent[v]);
    }
}