[백준] 17472. 다리 만들기 2 (MST구현/Java)

[백준] 17472. 다리 만들기 2

 

📌 풀이 과정

문제를 읽고 풀 엄두가 나지 않는다면 시리즈 1부터 푸는 것을 추천합니다..

[백준] 2146. 다리 만들기

 

이 문제는 여러개의 섬을 다리로 연결해 하나의 연결된 그래프를 만들고, 그 총 다리 길이의 최소값을 찾는 최소 신장 트리(MST) 문제이다.

 

BFS를 통해 각 섬을 구분한 후 섬 사이에 연결 가능한 다리를 계산한다. 최소값이 될 수도 있는 다리들을 우선순위 큐에 저장한 다음, 크루스칼 알고리즘을 통해 MST를 구현해 모든 섬이 하나로 연결되도록 하면 된다.

 

문제 조건

1. 다리의 방향이 바뀌면 안된다. 무조건 가로 or 세로

2. 다리의 길이는 2 이상이어야 한다.

모든  섬을 연결하는 다리 길이의 최솟값을 구해야 한다.

 

입력 값에서 섬은 모두 1로 주어지기 때문에 상하좌우로 인접한 1들의 집합은 하나의 섬으로 생각하면 된다.

 

1️⃣ 섬 구분하기

BFS를 사용해 모든 섬에 고유 번호를 부여한다.

각 섬을 방문하여 동일한 섬인 것을 식별하고 번호를 부여함으로써 이후의 다리 건설 시 출발 섬과 도착 섬을 명확히 구분할 수 있다.

그리고 이미 방문한 섬을 재탐색 하지 않도록 visited 배열을 두자.

private static void setIsland(int x, int y, int group) {
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[] { x, y });
    map[x][y] = group;
    visited[x][y] = true;

    while (!q.isEmpty()) {
         int[] cur = q.poll();
         x = cur[0];
         y = cur[1];

         for (int[] dir : d) {
              int nx = x + dir[0];
              int ny = y + dir[1];

              if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) continue;

              if (map[nx][ny] == 1) {
                  map[nx][ny] = group;
                  visited[nx][ny] = true;
                  q.add(new int[] { nx, ny });
              }
         }
    }
}

 

2️⃣ 다리 생성하기

섬의 각 좌표에서 직선으로만 상하좌우 방향으로 바다를 탐색해, 다른 섬에 도착할 경우 다리 길이를 저장한다.

조건을 만족하는 다리만 Bridge 객체로 생성해 우선순위 큐에 추가한다.

이 과정에서도 visited 배열을 초기화해 중복 방문을 방지하도록 한다.

private static void makeBridge(int startX, int startY, int group) {
 	visited = new boolean[N][M];

    for (int dir = 0; dir < 4; dir++) {
         Queue<int[]> q = new LinkedList<>();
         q.add(new int[] {startX, startY, 0});
         visited[startX][startY] = true;

         while (!q.isEmpty()) {
             int[] cur = q.poll();
             int x = cur[0];
             int y = cur[1];
             int depth = cur[2];

             int nx = x + d[dir][0];
             int ny = y + d[dir][1];

             if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) break;

             if(map[nx][ny] != group){
                  if(map[nx][ny] != 0){ // 다른 섬인 경우
                      if(depth >= 2){
                          pq.add(new Bridge(group, map[nx][ny], depth));
                          break;
                      }
                  }
                  else{ // 바다인 경우 계속 탐색
                      visited[nx][ny] = true;
                      q.add(new int[] { nx, ny, depth + 1 });
                  }
              }
         }
     }
}

 

3️⃣ MST - 크루스칼

크루스칼 알고리즘을 사용해서 모든 노드가 최소 비용으로 연결되도록 한다.

우선순위 큐에서 다리 길이가 짧은 순서대로 꺼내 섬을 연결한다.

두 섬이 이미 연결되었는지 확인하고, 연결되지 않은 경우 union 연산을 통해 하나의 그룹으로 합친다.

마지막으로 모든 섬이 연결되었는지 확인해야 한다.

// 3. MST - 크루스칼 : 모든 섬 잇기
private static void setParent(){
    parent = new int[islandCnt];
    for(int i = 1; i < islandCnt; i++) {
        parent[i] = i;
    }
}

private static int findParent(int x) {
    if(parent[x] == x) return x;
    return parent[x] = findParent(parent[x]);
}

private static void union(int a, int b) {
    int aRoot = findParent(a);
    int bRoot = findParent(b);

    if(aRoot == bRoot) return;
    parent[bRoot] = aRoot;
}

private static int shortestPath() {
    int sum = 0;

    while(!pq.isEmpty()) {
        Bridge tmp = pq.poll();
        if(findParent(tmp.start) != findParent(tmp.end)) {
            sum += tmp.length;
            union(tmp.start, tmp.end);
        }
    }

    // 4. 모든 섬이 연결되어 있는지 확인
    int root = findParent(1);
    for(int i = 2; i < islandCnt; i++){
        if(root != findParent(i)) return 0;
    }
    return sum;
}

 

 

✨ 제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 17472. 다리 만들기 2
 * 메모리 : 14348 KB
 * 시간 : 108 ms
 */
public class Main {
    static int N, M, islandCnt;
    static int[][] map;
    static boolean[][] visited;
    static int[][] d = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    static PriorityQueue<Bridge> pq = new PriorityQueue<>();;
    static int[] parent;

    static class Bridge implements Comparable<Bridge> {
        int start, end, length;

        Bridge(int start, int end, int length){
            this.start = start;
            this.end = end;
            this.length = length;
        }

        @Override
        public int compareTo(Bridge o) {
            return Integer.compare(this.length, o.length);
        }
    }

    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];
        visited = new boolean[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());
            }
        }

        // 1. 섬 구분하기
        islandCnt = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    setIsland(i, j, islandCnt++);
                }
            }
        }

        // 2. 건설할 수 있는 다리 구하기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] != 0) makeBridge(i, j, map[i][j]);
            }
        }

        // 3. MST - 크루스칼 : 모든 섬 잇기
        setParent();
        int answer = shortestPath();
        System.out.println(answer == 0? -1 : answer);

    }

    // 1. 섬 구분하기
    private static void setIsland(int x, int y, int group) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { x, y });
        map[x][y] = group;
        visited[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            x = cur[0];
            y = cur[1];

            for (int[] dir : d) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) continue;

                if (map[nx][ny] == 1) {
                    map[nx][ny] = group;
                    visited[nx][ny] = true;
                    q.add(new int[] { nx, ny });
                }
            }
        }
    }

    // 2. 건설할 수 있는 다리 구하기
    private static void makeBridge(int startX, int startY, int group) {
        visited = new boolean[N][M];

        for (int dir = 0; dir < 4; dir++) {
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[] {startX, startY, 0});
            visited[startX][startY] = true;

            while (!q.isEmpty()) {
                int[] cur = q.poll();
                int x = cur[0];
                int y = cur[1];
                int depth = cur[2];

                int nx = x + d[dir][0];
                int ny = y + d[dir][1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny]) break;

                if(map[nx][ny] != group){
                    if(map[nx][ny] != 0){ // 다른 섬인 경우
                        if(depth >= 2){
                            pq.add(new Bridge(group, map[nx][ny], depth));
                            break;
                        }
                    }
                    else{ // 바다인 경우 계속 탐색
                        visited[nx][ny] = true;
                        q.add(new int[] { nx, ny, depth + 1 });
                    }
                }
            }
        }
    }

    // 3. MST - 크루스칼 : 모든 섬 잇기
    private static void setParent(){
        parent = new int[islandCnt];
        for(int i = 1; i < islandCnt; i++) {
            parent[i] = i;
        }
    }

    private static int findParent(int x) {
        if(parent[x] == x) return x;
        return parent[x] = findParent(parent[x]);
    }

    private static void union(int a, int b) {
        int aRoot = findParent(a);
        int bRoot = findParent(b);

        if(aRoot == bRoot) return;
        parent[bRoot] = aRoot;
    }

    private static int shortestPath() {
        int sum = 0;

        while(!pq.isEmpty()) {
            Bridge tmp = pq.poll();
            if(findParent(tmp.start) != findParent(tmp.end)) {
                sum += tmp.length;
                union(tmp.start, tmp.end);
            }
        }

        // 4. 모든 섬이 연결되어 있는지 확인
        int root = findParent(1);
        for(int i = 2; i < islandCnt; i++){
            if(root != findParent(i)) return 0;
        }
        return sum;
    }

}

 

---

 

예전에 이 문제를 처음 봤을때 어떻게 풀어야 하는지 감도 안왔었는데

문제를 처음 보고 2개월이 지난 지금 !!

어떻게 문제를 해결해야 할지 대충 로직은 그려지지만,  차근차근 설계하는 능력이 부족하다는 것을 느꼈다.

고수가 되는 그날까지 부지런히 문제를 풀어야겠다는 다짐을 한다.🤓