[백준] 17472번. 다리 만들기 2(JAVA)

문제

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

---

풀이(40분)

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

public class Main {

    static final int INF = Integer.MAX_VALUE; // 무한대 값 상수로 선언

    static int n, m, answer;
    static int[] parent;
    static int[][] map;
    static int[] dx = {0, 0, -1, 1}; // 상하좌우
    static int[] dy = {-1, 1, 0, 0};
    static int[][] lengthMap;
    static PriorityQueue<Node> pq = new PriorityQueue<>();

    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());
        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());
            }
        }

        // 섬마다 그룹 번호 부여 (2번부터 시작)
        int groupNum = 2;
        int groupCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1) {
                    bfs(new Point(i, j), groupNum);
                    groupNum++;
                    groupCount++;
                }
            }
        }

        // 유니온 파인드 배열 초기화
        parent = new int[groupCount];
        for (int i = 0; i < groupCount; i++) {
            parent[i] = i;
        }

        // 섬 간 다리 길이 저장 배열 초기화
        lengthMap = new int[groupCount][groupCount];
        for (int i = 0; i < groupCount; i++) {
            Arrays.fill(lengthMap[i], INF);
        }

        // 모든 섬에서 다리 탐색
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] != 0) {
                    setBridgeLength(i, j);
                }
            }
        }

        // 다리 길이 정보를 우선순위 큐에 저장
        for (int i = 0; i < groupCount; i++) {
            for (int j = 0; j < groupCount; j++) {
                if (lengthMap[i][j] != INF) {
                    pq.add(new Node(i, j, lengthMap[i][j]));
                }
            }
        }

        // 크루스칼 알고리즘 수행
        answer = kruskal();

        // 모든 섬이 연결되었는지 확인
        int root = find(0);
        for (int i = 1; i < groupCount; i++) {
            if (find(i) != root) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(answer);
    }

    // BFS로 섬 그룹화
    static void bfs(Point start, int groupNum) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(start);
        map[start.row][start.col] = groupNum;

        while (!queue.isEmpty()) {
            Point current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current.row + dx[i];
                int ny = current.col + dy[i];
                if (isInBounds(nx, ny) && map[nx][ny] == 1) {
                    map[nx][ny] = groupNum;
                    queue.add(new Point(nx, ny));
                }
            }
        }
    }

    // 다리 길이 측정
    static void setBridgeLength(int row, int col) {
        int startGroup = map[row][col];
        for (int d = 0; d < 4; d++) {
            int nx = row + dx[d];
            int ny = col + dy[d];
            int length = 0;

            while (isInBounds(nx, ny)) {
                if (map[nx][ny] == startGroup) break; // 같은 섬이면 종료
                if (map[nx][ny] > 0) {
                    if (length >= 2) { // 다른 섬에 도달했고 길이가 2 이상
                        int endGroup = map[nx][ny];
                        int a = startGroup - 2;
                        int b = endGroup - 2;
                        lengthMap[a][b] = Math.min(length, lengthMap[a][b]);
                        lengthMap[b][a] = Math.min(length, lengthMap[b][a]);
                    }
                    break;
                }
                length++;
                nx += dx[d];
                ny += dy[d];
            }
        }
    }

    // 크루스칼 알고리즘 수행
    static int kruskal() {
        int total = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int aRoot = find(node.start);
            int bRoot = find(node.end);
            if (aRoot != bRoot) {
                union(aRoot, bRoot);
                total += node.length;
            }
        }
        return total;
    }

    // 유니온 파인드: 유니온
    static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            if (rootA < rootB) {
                parent[rootB] = rootA;
            } else {
                parent[rootA] = rootB;
            }
        }
    }

    // 유니온 파인드: 파인드 (경로 압축)
    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 지도 범위 체크
    static boolean isInBounds(int row, int col) {
        return row >= 0 && row < n && col >= 0 && col < m;
    }

    // 좌표 저장용 클래스
    static class Point {
        int row, col;
        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }

    // 다리 정보 클래스 (우선순위 큐용)
    static class Node implements Comparable<Node> {
        int start, end, length;
        public Node(int start, int end, int length) {
            this.start = start;
            this.end = end;
            this.length = length;
        }
        @Override
        public int compareTo(Node o) {
            return this.length - o.length; // 길이 기준 오름차순
        }
    }
}

---

문제 풀이 전략

 

문제 풀이 최초 계획은 그닥 어렵지 않았다. 아래 접은 글을 참고하자.

풀이가 바로 생각나는 경우 꼭 주석으로 작성해두고 진행하는 편이다.

// 다리는 일자여야한다.
    // 다리는 인접한 두 섬만을 연결할 수 있다(스쳐지나간다고 연결된 것은 아니다.)
    // 다리의 길이는 2 이상이어야 한다.
    // 다리는 교차할 수 있으나 이에 따라 길이는 중첩되는 것이다.(겹쳐진 부분에 대해서 모두 체크한다는 뜻)
    /*
    bfs로 그룹화
    -> 그룹화 하면서 키 : 그룹번호, 밸류리스트: 포인트

    모든 점에 대해 4방향 탐색으로 그룹 간 경로 찾기
    -> 2이상 중 최솟값으로 갱신
    -> 탐색 중 한번 도달하면 끝 도달 시 (뎊쓰-1)이 거리 -> 일단 배열에 저장 (배열은 int[그룹 개수][그룹 개수]
    -> 만약, 거리가 1(뎊쓰가 2)에서 끝나면 버림

    모든 경로에 대해 우선 순위 큐에 추가
    -> 우선 순위 큐는 (노드, 노드, 거리)이고, 거리에 대한 오름차순

    유니온 파인드를 위한 int[그룹 개수] 선언 및 자신을 부모로 초기화

    크루스칼로 뽑으면서 유니온 파인드
    -> 유니온은 그룹 번호 작은게 우선되게
    -> 파인드 호출이 많고 뎊쓰가 깊으므로 반드시 경로 압축
    -> 전역변수 answer에 거리 추가하면서 진행

    부모배열의 모든 인덱스에 대한 find(idx)
    -> 같다면 answer 출력 후 리턴
    -> 다르다면 -1 출력
     */

최소신장트리 를 알고 있다면 해당하게 진행만 해주면 되었다.

다만, 그 과정을 만들어 가는 부분이 복잡했다.

 

1. bfs를 활용하여 섬을 만들어준다.
   • 섬을 만들 때는 초기 입력값인 0,1을 효율적으로 사용하기 위하여 값을 2부터 매긴다.
   • 섬을 만드는 동안 총 섬의 개수를 저장한다.
2. 섬의 개수에 맞는 union용 배열을 만든다.
   • 1번을 통해 구한 groupCount를 이용하여 parent = new int[groupCount]로 만든다.
3. 모든 섬에 대해 가능한 다리를 찾는다.
   • 섬의 모든 영역에 대해 4방향 탐색을 진행하여 시작섬과 도착섬, 그리고 거리를 찾는다.
     • 이는 lengthMap[groupCount][groupCount]로 만든다.
       • 행은 출발섬, 열은 도착섬, 값은 거리를 갖는다.
4. 모든 다리에 대한 정보를 우선순위 큐에 넣고 크루스칼 알고리즘을 실행한다.
5. 모든 섬이 연결되어있다면 정답을, 아니라면 -1을 출력한다.