[BOJ][Java] 17472번 다리 만들기 2

문제 설명

문제 링크 : https://www.acmicpc.net/problem/17472

 

문제 설명이 아주 자세하게 나와있다.

일반적인 하나의 알고리즘을 이용하는 게 아닌 여러 알고리즘을 사용하여 해결할 수 있는 문제이다.

우선 문제에서 구하고자 하는것을 보면 결국 모든 섬이 하나의 집합으로 만들어져야 하는데

이때 최단거리를 구하는 문제이다.

 

얼핏 봤을 때 최소 신장 트리(MST) 알고리즘을 사용하면 될 것처럼 보인다.

일반적인 MST알고리즘 문제는 간선과 정점을 직접 제공하는경우가 많다.

하지만 이 문제에서는 아무것도 주어져있지 않다.

 

문제에서 주어진 그림을 자세히 보면 힌트를 주듯 각 섬을 하나의 번호로 묶은 것을 볼 수 있다.

따라서 문제를 해결하는 과정은 아래와 같다.

왼쪽과 같이 주어진 입력값을 오른쪽과 같이 변환한다.(BFS이용)

각각의 섬을 정점으로 보고 MST알고리즘을 사용한다.

1. 섬을 정점이라고 생각하고 맞닿아 있는 점끼리는 하나의 정점으로 취급한다.

2. 문제에 조건에 따라 일직선으로 연결되는 모든 다리(간선)와 그에 가중치를 구한다.

3. MST 알고리즘을 이용하여 해결한다.

4. 만약 섬이 연결되어있지 않다면(다리의 개수가 섬의 개수 - 1개가 아니라면) -1을 연결되어 있다면 최단거리를 출력한다.

 

package boj;

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

public class BOJ17472 {
    static int[][] arr;
    static int island = 2;
    static int N;
    static int M;
    static int[] heads;
    static List<Edge> edges = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N][M];

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

        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(arr[i][j] == 1){
                    bfs(i,j);
                }
            }
        }

        make();

        // 최소 신장 트리 수행
        edges.sort((o1,o2) -> o1.cost - o2.cost);

        heads = new int[island];
        for(int i = 0; i < heads.length; i++){
            heads[i] = i;
        }
        int count = 0;
        int answer = 0;


        for(int i = 0; i < edges.size(); i++){
            Edge now = edges.get(i);
            if(find(now.node1) != find(now.node2)){
                union(now.node1, now.node2);
                count++;
                answer += now.cost;
            }
        }

        if(count != island -3) System.out.println(-1);
        else System.out.println(answer);

    }
    static int find(int num){
        if(num == heads[num]) return num;
        return heads[num] = find(heads[num]);
    }

    static void union(int a, int b){
        int aHead = find(a);
        int bHead = find(b);

        if(aHead != bHead) heads[bHead] = aHead;
    }

    static void make(){
        // 열별로 실행
        for(int j = 0; j < M; j++){
            int count = 0;
            int before = 0;
            for(int i = 0; i < N; i++){
                if(arr[i][j] != 0){    // 0이 아닌경우
                    if(before != arr[i][j] && count >= 2){
                        edges.add(new Edge(before, arr[i][j], count));
                        before = arr[i][j];
                        count = 0;
                    }else{
                        before = arr[i][j];
                        count = 0;
                    }
                }else{                 // 0인 경우
                    if(before == 0) continue;
                    count++;
                }
            }
        }

        // 행별로 실행
        for(int i = 0; i < N; i++){
            int count = 0;
            int before = 0;
            for(int j = 0; j < M; j++){
                if(arr[i][j] != 0){    // 0이 아닌경우
                    if(before != arr[i][j] && count >= 2){
                        edges.add(new Edge(before, arr[i][j], count));
                        before = arr[i][j];
                        count = 0;
                    }else{
                        before = arr[i][j];
                        count = 0;
                    }
                }else{                 // 0인 경우
                    if(before == 0) continue;
                    count++;
                }
            }
        }
    }



    static void bfs(int i, int j){
        int[] di = {1,0,-1,0};
        int[] dj = {0,1,0,-1};
        Queue<Node> q = new LinkedList<>();
        arr[i][j] = island;
        q.add(new Node(i,j));

        while(!q.isEmpty()){
            Node now = q.poll();

            for(int d = 0; d < 4; d++){
                int ni = now.i + di[d];
                int nj = now.j + dj[d];

                if(0 <= ni && ni < N && 0 <= nj && nj < M && arr[ni][nj] == 1){
                    arr[ni][nj] = island;
                    q.add(new Node(ni,nj));
                }
            }
        }

        island++;
    }

    static class Node{
        int i;
        int j;

        public Node(int i, int j){
            this.i = i;
            this.j = j;
        }
    }

    static class Edge {
        int node1;
        int node2;
        int cost;

        public Edge(int node1, int node2, int cost){
            this.node1 = node1;
            this.node2 = node2;
            this.cost = cost;
        }

        public String toString(){
            return ""+ node1 + " " + node2 + " " + cost;
        }
    }
}