[BOJ] 17472. 다리만들기2 (Java)

[BOJ] 17472. 다리만들기2 (Java)

Problem

제출일 : 2020-04-14

문제 풀이 시간 : 2H 30M

난이도 : ★★★☆

---

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

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

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

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

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

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

다리의 총 길이: 13D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다.	다리의 총 길이: 9 (최소)

다음은 올바르지 않은 3가지 방법이다

C의 방향이 중간에 바뀌었다	D의 길이가 1이다.	가로 다리인 A가 1과 가로로 연결되어 있지 않다.

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

A의 길이는 4이고, B의 길이도 4이다.총 다리의 총 길이: 4 + 4 + 2 = 10	다리 A: 2와 3을 연결 (길이 2)다리 B: 3과 4를 연결 (길이 3)다리 C: 2와 5를 연결 (길이 5)다리 D: 1과 2를 연결 (길이 2)총 길이: 12

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

Constraints

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

Input

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

Output

테스트 케이스의 개수 만큼 T개의 줄에 각 테스트 케이스에 대한 답을 출력한다.

각 줄은 “#x”로 시작하고, 공백을 하나 둔 후 정답을 출력한다. (x는 테스트 케이스의 번호이며, 1번부터 시작한다.)

출력해야 할 정답은 M시간 후 남아 있는 미생물 수의 총 합이다.

Example

input

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

output

9

Solution & Inpression

문제 풀이 순서

1. 입력 받은 map의 섬의 개수를 파악하며 섬에 번호를 붙여준다 (DFS)
2. 각 섬에서 출발하여 도착 가능한 섬에 건설할수 있는 최소비용을 찾는다. (BFS)
3. 모든 섬을 연결하는 다리 길이의 최솟값을 구한다(MST:최소신장트리)

이 문제는 완전탐색, 너비우선탐색, 깊이우선탐색, 그래프이론, 최소신장트리를 이용하여 구현하는 문제로 문제의 난이도가 높다.

Code

언어 : JAVA

메모리 : 14512 kb

실행시간 : 116ms

package BOJ.Graph;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;


public class Gold3_17472_다리만들기2 {
    static int N, M;
    static int[][] map;

    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    static int[] parent;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 1)
                    map[i][j] = -1;
            }
        }

        // 맵 라밸링 맵의개수 파악
        int island = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == -1) {
                    DFS(i, j, island++);
                }
            }
        }

        // 간선의 비용 구하기
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2];
            }
        });

        for (int i = 1; i < island; i++) {
            for (int j = i + 1; j < island; j++) {
                int cost = getBridge(i, j);
                if (cost != 0)
                    pq.add(new int[] { i, j, cost });
            }
        }

        // makeSet
        parent = new int[island];
        for (int i = 1; i < island; i++) {
            parent[i] = i;
        }

        int ans = 0;
        // 다리선택 MST
        while (!pq.isEmpty()) {
            int[] now = pq.poll();
            int x = find(now[0]);
            int y = find(now[1]);
            if (x != y) {
                union(now[0], now[1]);
                ans += now[2];
            }
        }

        // 결과
        boolean flag = true;
        for (int i = 1; i < island; i++) {
            if (find(i) != 1) {
                flag = false;
                break;
            }
        }
        System.out.println(flag ? ans : -1);
    }

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

        if (x > y)
            parent[x] = y;
        else
            parent[y] = x;
    }

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

    private static int getBridge(int start, int end) {
        boolean[][][] visit = new boolean[N][M][4];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != start)
                    continue;
                for (int k = 0; k < dr.length; k++) {
                    int r = i + dr[k];
                    int c = j + dc[k];
                    if (!isRange(r, c) || map[r][c] != 0)
                        continue;
                    q.add(new int[] { r, c, 0, k });
                    visit[r][c][k] = true;
                }
            }
        }

        int ret = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            if (map[now[0]][now[1]] == end) {
                if (now[2] == 1)
                    continue;
                ret = now[2];
                break;
            }
            int nr = now[0] + dr[now[3]];
            int nc = now[1] + dc[now[3]];

            if (isRange(nr, nc) && !visit[nr][nc][now[3]]
                    && (map[nr][nc] == 0 || map[nr][nc] == end)) {
                visit[nr][nc][now[3]] = true;
                q.add(new int[] { nr, nc, now[2] + 1, now[3] });
            }
        }

        return ret;
    }

    private static void DFS(int i, int j, int cnt) {
        map[i][j] = cnt;
        for (int k = 0; k < dc.length; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];
            if (isRange(nr, nc) && map[nr][nc] == -1) {
                DFS(nr, nc, cnt);
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < N && 0 <= nc && nc < M)
            return true;
        return false;
    }
}