백준 다리 만들기 2 17472 Java (Gold 1)

문제 요약

NxM 지도는 땅과 바다로 이루어져 있다. 

이때 땅은 섬으로, 이 섬들을 다리로 연결해야한다. 

다리는 최소 길이(격자에서 차지하는 칸의 수) 가 2여야하며, 바다에만 건설이 가능하다.

다리의 양 끝은 섬과 인접한 바다에 있어야한다.

아래 그림에서 B는 다리가 맞지만 A는 올바른 다리가 아니다.

가로 다리인 A가 1과 가로로 연결되어 있지 않다.

방향은 중간에 꺾일수가 없다. 즉 가로 다리와 세로 다리만 존재한다.

다리는 교차로 설치가 가능하다. 

 

• 입력:
  
  • 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 
    • 1 ≤ N, M ≤ 10
    • 3 ≤ N×M ≤ 100
  • 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
    • 2 ≤ 섬의 개수 ≤ 6
• 출력:
  • 다리 길이의 최솟값을 return한다. 모든 섬이 연결이 불가능하다면 -1을 출력한다.

접근 방식

 

BFS , MST( 유니온 파인드) 를 사용하며 풀었다. 

예제 입력방식을 보면서 이해해보자

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

 

지도를 보면 1은 섬, 0은 바다 이다.

먼저 섬을 먼저 구분해야한다. 1번섬, 2번섬...etc : BFS 사용

그리고 섬을 구분했으면 가로, 세로 별 가능한 다리를 queue에 넣는다 (다리 길이>=2인 것 만)

ex) (1,2,5) : 1번섬과 2번섬을 잇는 길이가 5인 다리가 존재한다. 의미 

 

그치만 여기서 MST를 사용한다면 최소한의 거리를 사용하여 다리를 이을수가 있다. 

그래서 큐가 아니라 거리 기준으로 오름차순 정렬한 우선순위큐를 사용해서 해결한다. 

이때 다리를 이을지 말지는 크루스칼의 방법(유니온파인드)를 사용하여 해결하였다. 

둘의 부모가 같지 않다면 다리를 잇고, 부모가 같다면 굳이 이을 필요가 없다.

 

마지막으로 전체 부모가 1이아니라면 모든 다리를 잇지 못했으므로 -1을 반환하면 된다. 

 

작성한 코드는 다음과 같다.

import java.io.*;
import java.util.*;
class Bridge implements Comparable<Bridge> {
    int from;
    int to;
    int distance;

    public Bridge(int from, int to, int distance){
        this.from =from;
        this.to=to;
        this.distance= distance;
    }
    @Override
    public int compareTo(Bridge o){
        if(this.distance==o.distance){
            return this.from-o.from;
        }
        return this.distance-o.distance;
    }
}

public class Main {
    static int n, m;
    static int[][] map, island;
    static int[] parent;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        island = new int[n][m]; //0: 바다, 숫자는 섬의 번호
        int islandCnt =1; //섬 번호
        for(int i =0;i<n;i++){
            st = new StringTokenizer(bf.readLine());
            for (int j =0;j<m;j++){
                map[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        //섬의 번호 넘버링
        for(int i =0;i<n;i++){
            for (int j =0;j<m;j++){
                // 섬인데 방문안했다면..
                if(map[i][j]==1 && island[i][j]==0){
                    bfs(i,j,islandCnt);
                    islandCnt++;
                }
            }
        }

        PriorityQueue<Bridge> pq = new PriorityQueue<>();

        // 가로 다리
        for(int i =0;i<n;i++){
            boolean first = false;
            int[] memo = new int[2]; // 섬번호, j 좌표
            for (int j =0;j<m;j++){
                if(map[i][j]==1 && !first){
                    first =true;
                    memo[0]= island[i][j];
                    memo[1]=j;
                }else if (map[i][j]==1 && island[i][j]==memo[0]){
                    memo[1]=j;
                } else if (map[i][j]==1 && island[i][j]!=memo[0] ){ // 다른섬 ...
                    int distmp =j-memo[1]-1;
                    if(distmp>1){
                        pq.add(new Bridge(memo[0], island[i][j],distmp ));
                    }

                    memo[0]= island[i][j];
                    memo[1]=j;
                }
            }
        }

        // 세로 다리
        for (int j =0;j<m;j++){
            boolean first = false;
            int[] memo = new int[2]; // 섬번호, j 좌표
            for(int i =0;i<n;i++){
                if(map[i][j]==1 && !first){
                    first =true;
                    memo[0]= island[i][j];
                    memo[1]=i;
                }else if (map[i][j]==1 && island[i][j]==memo[0]){
                    memo[1]=i; // 같은 섬
                } else if (map[i][j]==1 && island[i][j]!=memo[0] ){ // 다른섬 ...
                    int distmp =i-memo[1]-1;
                    if(distmp>1){
                     pq.add(new Bridge(memo[0], island[i][j],distmp ));
                    }

                    memo[0]= island[i][j];
                    memo[1]=i;
                }
            }
        }

        // 다리들의 연결 여부를 파악하기 위해 유니온 파인드를 사용
        parent = new int[islandCnt];
        for(int i =1;i<islandCnt;i++){
            parent[i]=i;
        }

        int answer =0;
        while(!pq.isEmpty()){
            Bridge q = pq.poll();
            int a = q.from;
            int b =q.to;
            int d =q.distance;

            int fa = find(a);
            int fb = find(b);

            // 이미 연결되어있음
            if(fa==fb){
                continue;
            }else if (fa<fb){
                answer+=d;
                parent[fb]= fa;
            }else{
                answer+=d;
                parent[fa]=fb;
            }

        }
        boolean avail =true;
        for(int i =1;i<islandCnt;i++){
            if(parent[find(i)]!=1){
                avail=false;
                break;
            }
        }
        if(!avail){
            System.out.println(-1);
        }else{
            System.out.println(answer);
        }
    }

    private static void bfs (int startX, int startY, int num){
        island[startX][startY] =num;

        for(int di=0; di<4;di++){
            int x =  startX +dx[di];
            int y = startY+dy[di];
            if(x<0 || y<0|| x>=n || y>=m ||map[x][y]==0 || island[x][y]!=0){
                continue;
            }
            bfs(x,y,num);
        }
    }

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

}

 

Eug2n2's GitHub