[백준] 17472번 : 다리 만들기 2 - 자바(JAVA)

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

17472번: 다리 만들기 2

 

문제 해석

섬으로 이루어진 나라가 존재하고 모든 섬을 다리로 연결하려고 합니다.

 

이 나라의 지도는 N x M 크기의 이차원 격자로 나타잴 수 있으며 격자의 각 칸은 땅이거나 바다입니다.

 

파란색은 땅을 의미합니다.

 

다리를 놓아 섬A와 섬B를 연결하고자 할때 제약사항은 다음과 같습니다.

• 다리는 바다에만 건설할 수 있습니다.
• 다리의 길이는 2 이상이여야 합니다.
• 다리는 방향이 중간에 바뀌면 안됩니다.
• 다리의 양 끝은 섬과 인접한 바다 위에 있어야 합니다.
• 방향이 가로인 다리는 양 끝이 가로 방향으로 섬과 인접해야 합니다.
• 방향이 세로인 다리는 양 끝이 세로 방향으로 섬과 인접해야 합니다.

 

 

 

다리가 겹치는 경우에 길이를 계산하는 방법은 다음과 같습니다.

모든 섬을 연결하는 다리 길이의 최솟값을 출력하세요

모든 섬을 연결하는 것이 불가능하면 -1을 출력하세요

 

 

문제 풀이 전 설계

N, M 의 범위가 1~10 사이이므로 완전탐색쪽으로 접근해 보고자 합니다.

스도쿠 문제처럼 빈칸을 저장하여 임의의 빈칸 2개를 선정하여 다리를 놓아보는 방식의 백트레킹을 사용하고자 합니다.

 

문제 풀이하면서

어떻게 풀어야하나 계속 고민했었는데 

각 섬을 노드 N으로 보고 이중 N-1개의 다리를 골라 모두 이어지며 만들며 최소의 값을 구해야 하는 문제입니다.

즉, mst 최소 신장 트리 문제였습니다.

 

1. 섬 번호 매기기 (BFS or DFS 사용)

2. 섬 그래프 생성

3. 프림알고리즘으로 MST 구하기

 

코드

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

public class Main_17472_다리만들기2 {

    static boolean[][] visited;
    static boolean[] landVisited;
    static int[][] board,graph;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int M, N,mapNumbering;
    static int linkedCount,sum;
    static class Pos {
        int y;
        int x;

        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static class Edge implements Comparable<Edge> {
        int to;
        int weight;

        public Edge(int to, int weight) {

            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    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][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //섬 번호 매기기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (board[i][j] == 0 || visited[i][j]) {
                    continue;
                }
                bfs(i, j);
            }
        }
/*
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
*/

        //그래프 생성
        graph = new int[mapNumbering+1][mapNumbering+1];

        for(int i=1; i<=mapNumbering; i++){
            for(int j=1; j<=mapNumbering; j++){
                graph[i][j] = Integer.MAX_VALUE;
            }
        }

        // 생성된 그래프의 간선을 연결
        for(int i=0; i< N; i++){
            for(int j=0; j<M; j++){
                //바다면 continue
                if(board[i][j] == 0){
                    continue;
                }
                //만약 도시라면
                for(int k=0; k<4; k++){
                    int tempY = i + dy[k];
                    int tempX = j + dx[k];
                    if(!isValidPos(tempY,tempX)){
                        continue;
                    }
                    if(board[tempY][tempX] != 0){
                        continue;
                    }
                    //해당 방향으로 쭉 다리 이어보기
                    makeGraph(new Pos(i,j), new Pos(tempY,tempX), k, 1);

                }
            }
        }
/*
        for (int i = 1; i <= mapNumbering; i++) {
            for (int j = 1; j <= mapNumbering; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
*/
        //프림알고리즘 시작
        landVisited = new boolean[mapNumbering+1];
        prim(1);
        boolean isAllvisited = true;
        for(int i=1; i<=mapNumbering; i++){
            if(!landVisited[i]){
                isAllvisited = false;
            }
        }
        if(isAllvisited) {
            System.out.println(sum);
            return;
        }
        System.out.println(-1);
    }

    private static void bfs(int i, int j) {
        mapNumbering++;

        visited[i][j] = true;
        Queue<Pos> bfsQ = new LinkedList<>();
        bfsQ.add(new Pos(i, j));

        while (!bfsQ.isEmpty()) {
            Pos curPos = bfsQ.poll();
            board[curPos.y][curPos.x] =  mapNumbering;

            for (int k = 0; k < 4; k++) {
                int tempY = curPos.y + dy[k];
                int tempX = curPos.x + dx[k];
                if (!isValid(tempY, tempX)) {
                    continue;
                }

                visited[tempY][tempX] = true;
                bfsQ.add(new Pos(tempY, tempX));
            }
        }
    }

    private static boolean isValid(int tempY, int tempX) {
        return tempY >= 0 && tempY < N && tempX >= 0 && tempX < M && !visited[tempY][tempX] && board[tempY][tempX] != 0;
    }

    private static void makeGraph(Pos start, Pos cur, int dir, int cnt){
        int nextY = cur.y + dy[dir];
        int nextX = cur.x + dx[dir];
        if(!isValidPos(nextY,nextX)){
            return;
        }
        if(board[nextY][nextX] == 0){
            makeGraph(start,new Pos(nextY,nextX), dir, cnt+1);
        } else{
            int s = board[start.y][start.x];
            int e = board[nextY][nextX];
            if(s==e){
                return;
            }
            if( cnt >=2){
                if(graph[s][e] > cnt){
                    graph[s][e] = cnt;
                    graph[e][s] = cnt;
                }
            }

        }

    }

    private static boolean isValidPos(int y, int x) {
        return y>=0 && x >=0 && y<N && x <M;
    }

    private static void prim(int start) {

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start,0));
        //1부터 시작
        while(!pq.isEmpty()) {
            Edge curEdge = pq.poll();
            //이미 연결된 노드면 더이상 검사 x
            if(landVisited[curEdge.to]){
                continue;
            }
            linkedCount++;
            sum += curEdge.weight;
            landVisited[curEdge.to] = true;

            if(linkedCount == mapNumbering){
                break;
            }

            for (int i = 1; i <= mapNumbering; i++) {
                if (landVisited[i]) {
                    continue;
                }
                if(graph[curEdge.to][i] == Integer.MAX_VALUE){
                    continue;
                }

                pq.add(new Edge(i, graph[curEdge.to][i]));
            }
        }

    }
}