[백준 Gold 2] 17472 다리 만들기 2 - Java

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

17472번: 다리 만들기 2

 

접근 과정 : 

• 크게 4개의 과정으로 문제를 해결하려고 했다.
• input() : 입력을 받는 단계. N,M을 입력받고 그에 따라 Map[][] 입력받는다.
• defindLand() : 섬을 정의하고 구분한다.  섬에 번호를 붙여 구분한다.
• serarchBridge() : 섬들 사이에 연결할 수 있는 모든 다리를 구한다.
• minBridges() : 앞서서 구한 다리들을 길이가 작은 다리부터 연결해가면서 최소 다리 길이를 계산한다.

 

소스 코드 및 결과 :

 

package BOJ;

/* 
    다리 만들기 2

*/

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

public class BOJ17472 {

    public static void main(String[] args) throws IOException {

        input();

        defindLand();

        searchBridge();

        int answer = minBridges();

        System.out.println(answer);

    }

    static int N, M, land;
    static int[][] map;
    static boolean[][] visit;
    static int[][] move = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    static List<int[]> bridge;
    static int[] group;

    static void input() 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());

        map = new int[N][M];

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

    static void defindLand() {
        int idx = 1;
        visit = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 && !visit[i][j]) {
                    dfsForDefine(i, j, idx);
                    idx++;
                }
            }
        }

        land = idx - 1;
    }

    static void dfsForDefine(int i, int j, int idx) {
        map[i][j] = idx;
        visit[i][j] = true;

        for (int d = 0; d < 4; d++) {
            int x = i + move[d][0];
            int y = j + move[d][1];

            if (x < 0 || x >= N || y < 0 || y >= M) {
                continue;
            }

            if (visit[x][y] || map[x][y] != 1) {
                continue;
            }

            dfsForDefine(x, y, idx);
        }
    }

    static void searchBridge() {

        bridge = new ArrayList<>();

        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) {
                    queue.add(new int[] { i, j, map[i][j] });
                }
            }
        }

        while (!queue.isEmpty()) {

            int[] now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int x = now[0] + move[i][0];
                int y = now[1] + move[i][1];

                int count = 0;
                while (true) {
                    if (x < 0 || x >= N || y < 0 || y >= M || map[x][y] == now[2]) {
                        break;
                    }

                    if (map[x][y] > now[2]) {
                        if (count >= 2) {
                            bridge.add(new int[] { now[2], map[x][y], count });
                        }
                        break;
                    }

                    x += move[i][0];
                    y += move[i][1];
                    count++;

                }

            }

        }

    }

    static int minBridges() {
        int distance = 0;
        group = new int[land + 1];

        Collections.sort(bridge, (a, b) -> {
            return a[2] - b[2];
        });

        int count = 0;

        for (int[] b : bridge) {

            int x = findGroup(b[0]);
            int y = findGroup(b[1]);

            if (x == y) {
                continue;
            }

            distance += b[2];
            group[y] = x;
            count++;

            if (count == land - 1) {
                return distance;
            }
        }
        return -1;

    }

    static int findGroup(int x) {
        if (group[x] == 0) {
            return x;
        }

        return group[x] = findGroup(group[x]);
    }

}

 

P.S 

좀더 식별하기 쉽게 코드를 작성하려고 했다.

문제를 보고 단계를 구분해며, 그에 따라 메소드를 나눠서 작성했다.

 

요즘... java 11에 비해서 java 8 의 속도다 훨씬 느리게 작성되고 있다...

내가 java 11에 익숙해진건지.. 효율성을 잃어버린건지..