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

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

17472번: 다리 만들기 2

문제

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

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

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

유형 : 구현 + 그래프 탐색 + MST

 

접근 방식

• 섬에 대한 구분 : BFS를 통해 섬에 번호를 매긴다.
• 다리 건설 : BFS를 통해 다른 섬하고의 거리 계산 
  • 다리가 중간에 꺽이면 안된다. (다리의 방향이 한가지여야만 한다.)
  • 다리의 길이가 2이상이여야 한다.
• 섬을 모두 연결하는 데 필요한 다리의 개수 : 섬의 개수 - 1개
  • 즉 MST를 만들어야 한다.

섬에 대한 구분 : BFS

static void find(int num,int x,int y){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));
        land[x][y] = num; // 섬의 번호 지정
        landPoint[num].add(new Point(x,y,-1)); // 다리 건설을 위해 사용할 데이터

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

            for(int i=0;i<4;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;
                    
				// 아직 탐색되지 않은 섬의 일부라면
                if(land[nx][ny] == 0 && board[nx][ny] == 1){
                    land[nx][ny] = num;
                    q.add(new Node(nx,ny));
                    landPoint[num].add(new Point(nx,ny,-1));
                }
            }
        }
    }

다리 건설

    static void dis(int num){
        int[][][] dis = new int[n+1][m+1][4];
        while(!landPoint[num].isEmpty()){
            Point cur = landPoint[num].poll();
            
            // 섬에서 다리 시작
            if(cur.d == -1){
                for(int i =0;i < 4;i++){
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];

                    if(nx < 1 || nx > n || ny < 1 || ny > m)
                        continue;

                    if(land[nx][ny] != 0)
                        continue;

                    if(dis[nx][ny][i] == 0){
                        dis[nx][ny][i] = 1;
                        landPoint[num].add(new Point(nx,ny,i));
                    }
                }
            }
            // 다리에서 다리
            else{
                int nx = cur.x + dx[cur.d];
                int ny = cur.y + dy[cur.d];

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;

                if(land[nx][ny] == num)
                    continue;

                if(dis[nx][ny][cur.d] == 0){
                    if(land[nx][ny] == 0){
                        dis[nx][ny][cur.d] = dis[cur.x][cur.y][cur.d] + 1;
                        landPoint[num].add(new Point(nx,ny,cur.d));
                    }

                    else{
                        // MST를 위해 사용할 데이터 : 다리의 길이가 2 이상이라면 간선의 정보 추가
                        if(dis[cur.x][cur.y][cur.d] >= 2){
                            pq.add(new Point(num,land[nx][ny],dis[cur.x][cur.y][cur.d]));
                        }
                    }
                }
            }
        }
    }

MST

    static int find(int x){
        if(root[x] == x)
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y){
            root[y] = x;
        }

        else{
            root[x] = y;
        }
    }
    
    public static void main(String[] args) throws IOException{
        int count = 0;
        int result = 0;
        while(!pq.isEmpty()){
            Point cur = pq.poll();

            if(find(cur.x) != find(cur.y)){
                count += 1;
                result += cur.d;
                union(cur.x,cur.y);
            }

            if(count == num -1)
                break;
        }

        if(count == num -1){
            System.out.println(result);
        }

        else{
            System.out.println(-1);
        }
  }

전체 코드

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

public class Main {

    static int n = 0;
    static int m = 0;

    static int[][] board;
    static int[][] land;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    static Queue<Point>[] landPoint = new LinkedList[7];

    static PriorityQueue<Point> pq = new PriorityQueue<>(
            (x,y) -> x.d - y.d
    );

    static int[] root;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        board = new int[n+1][m+1];
        land = new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine()," ");

            for(int j=1;j<=m;j++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1;i<=6;i++){
            landPoint[i] = new LinkedList<Point>();
        }

        int num = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(board[i][j] == 1 && land[i][j] == 0){
                    find(num,i,j);
                    num = num + 1;
                }
            }
        }

        root = new int[num+1];

        num = num - 1;
        for(int i=1;i<=num;i++){
            root[i] = i;
            dis(i);
        }

        int count = 0;
        int result = 0;
        while(!pq.isEmpty()){
            Point cur = pq.poll();

            if(find(cur.x) != find(cur.y)){
                count += 1;
                result += cur.d;
                union(cur.x,cur.y);
            }

            if(count == num -1)
                break;
        }

        if(count == num -1){
            System.out.println(result);
        }

        else{
            System.out.println(-1);
        }

        br.close();
    }

    static void print(){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(land[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    static void find(int num,int x,int y){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));
        land[x][y] = num;
        landPoint[num].add(new Point(x,y,-1));

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

            for(int i=0;i<4;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;

                if(land[nx][ny] == 0 && board[nx][ny] == 1){
                    land[nx][ny] = num;
                    q.add(new Node(nx,ny));
                    landPoint[num].add(new Point(nx,ny,-1));
                }
            }
        }
    }
    static int find(int x){
        if(root[x] == x)
            return root[x];

        return root[x] = find(root[x]);
    }

    static void union(int x,int y){
        x = find(x);
        y = find(y);

        if(x < y){
            root[y] = x;
        }

        else{
            root[x] = y;
        }
    }

    static void dis(int num){
        int[][][] dis = new int[n+1][m+1][4];
        while(!landPoint[num].isEmpty()){
            Point cur = landPoint[num].poll();

            // 섬에서 다리 시작
            if(cur.d == -1){
                for(int i =0;i < 4;i++){
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];

                    if(nx < 1 || nx > n || ny < 1 || ny > m)
                        continue;

                    if(land[nx][ny] != 0)
                        continue;

                    if(dis[nx][ny][i] == 0){
                        dis[nx][ny][i] = 1;
                        landPoint[num].add(new Point(nx,ny,i));
                    }
                }
            }
            // 다리에서 다리
            else{
                int nx = cur.x + dx[cur.d];
                int ny = cur.y + dy[cur.d];

                if(nx < 1 || nx > n || ny < 1 || ny > m)
                    continue;

                if(land[nx][ny] == num)
                    continue;

                if(dis[nx][ny][cur.d] == 0){
                    if(land[nx][ny] == 0){
                        dis[nx][ny][cur.d] = dis[cur.x][cur.y][cur.d] + 1;
                        landPoint[num].add(new Point(nx,ny,cur.d));
                    }

                    else{
                        // MST를 위해 사용할 데이터 : 다리의 길이가 2 이상이라면 간선의 정보 추가
                        if(dis[cur.x][cur.y][cur.d] >= 2){
                            pq.add(new Point(num,land[nx][ny],dis[cur.x][cur.y][cur.d]));
                        }
                    }
                }
            }
        }
    }
}
class Node{
    int x;
    int y;

    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}
class Point{
    int x;int y;int d;

    Point(int x,int y,int d){
        this.x = x;
        this.y = y;
        this.d = d;
    }
}