[백준 17472번] 다리 만들기 2 - 그래프 탐색, 최소 신장 트리

[백준 17472번] 다리 만들기 2 - 그래프 탐색, 최소 신장 트리코딩테스트/백준2024. 7. 20. 17:31@mag1c

Table of Contents

728x90

문제 난이도

GOLD I (링크)

문제 풀이

각각의 독립된 섬들을 최단 거리로 연결하고 싶을 때, 놓을 수 있는 다리의 총 길이의 최소값을 구하는 문제.

역시나 최소 신장 트리를 응용한 문제가 되겠다.

이번에는 각 간선을 구하는 것과 더불어, 이 섬이 어느 정점인지를 구하는 것도 필요하다.

결국엔 두 정점 사이의 간선을 구해서 문제를 풀어야하기 때문이다.

위의 그림처럼 문제에서 요한 3가지 올바르지 않은 방법과 함께, 추가로 두 가지만 주의한다면 쉽게 풀 수 있다.

처음 다른 섬을 만났을 때 만족하지 않는 조건이라면 바로 빠져나올 것.

부끄럽게도 처음 코드를 완성시켰을 때, 다른 섬을 만났을 때, 종료 조건을 부족하게 작성하여 아래 그림처럼 더이상 탐색하지 못함에도 불구하고 탐색을 시켰다.

Union Find가 끝난 후 모두 연결 되어있는지 확인할 것

이 부분은 Find를 한번 더 사용하면 쉽게 해결할 수 있다.

~~나는 이 두 가지 때문에 40분 정도 계속 틀렸다.~~

정리하자면

우리는 처음으로 만나는 같은 직선상의 다른 섬에 길이 2 이상의 다리를 놓을 수 있는 경우의 수를 판별하면 된다.

풀이 단계

나는 아래와 같은 순서로 문제를 풀었다.

1. 섬을 식별할 수 있는 번호를 부여해 줄 그래프 탐색(bfs)을 통해 각 정점을 구함

//islandCnt를 통해 정점을 표현하여
// islandsMap이라는 섬 지도에 연결된 섬인지를 표현

//기존 지도 map
int[][] map;

int islandCnt = 0;
int[][] islandsMap = new int[N][M];
boolean[][] isVisit = new boolean[N][M];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (map[i][j] == 1 && !isVisit[i][j]) {
            islandCnt++;
            bfs(map, islandsMap, isVisit, N, M, i, j, islandCnt);
        }
    }
}


private static void bfs(int[][] map, int[][] islandsMap,
		boolean[][] isVisit, int N, int M, int x, int y, int cnt) {
    isVisit[x][y] = true;
    Queue<int[]> que = new LinkedList<>();
    que.offer(new int[] { x, y });
    //어느 정점인지를 표현
    islandsMap[x][y] = cnt;

    while (!que.isEmpty()) {
        int[] cur = que.poll();

        for (int i = 0; i < 4; i++) {
            int newX = cur[0] + dx[i];
            int newY = cur[1] + dy[i];

            if (isAvailableIdx(newX, newY, N, M) && !isVisit[newX][newY] && map[newX][newY] == 1) {
                isVisit[newX][newY] = true;
                islandsMap[newX][newY] = cnt;
                que.offer(new int[] { newX, newY });
            }

        }
    }
}

2. 연결 가능한 정점들끼리 연결

문제 조건에 맞게, 조건들을 설정하여 탐색을 통해 연결 가능한 섬들을 추출했다.

List<Bridge> bridges = findBridges(map, islandsMap, N, M);

private static List<Bridge> findBridges(int[][] map, int[][] islandsMap, int N, int M) {
    List<Bridge> bridges = new ArrayList<>();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            //1. 섬이 있을 경우에만 탐색
            if (islandsMap[i][j] > 0) {
                int number = islandsMap[i][j];

                //2. bfs와 유사하게 직선 방향으로만 탐색
                for (int k = 0; k < 4; k++) {
                    int length = 0;
                    int x = i;
                    int y = j;

                    while (true) {
                        x += dx[k];
                        y += dy[k];

                        //아래의 경우 탐색하지 않는다
                        //  3. 같은 정점(섬 그룹)에 속하거나
                        //  4. 길이가 1인 다른 섬의 경우
                        if (!isAvailableIdx(x, y, N, M) || islandsMap[x][y] == number
                                || (length <= 1 && map[x][y] == 1))
                            break;

                        if (islandsMap[x][y] > 0 && length >= 2) {
                            bridges.add(new Bridge(number, islandsMap[x][y], length));
                            break;
                        }
                        length++;
                    }
                }
            }
        }
    }

    return bridges;
}

3. 크루스칼 알고리즘을 통한 최소 신장 트리의 가중치를 구함

 Collections.sort(bridges, (o1, o2) -> o1.cost - o2.cost);

int[] parent = new int[islandCnt + 1];

for (int i = 0; i < islandCnt + 1; i++) {
    parent[i] = i;
}

int mstCost = 0;

for (Bridge b : bridges) {
    int s = b.start;
    int e = b.end;

    if (find(parent, s) != find(parent, e)) {
        union(parent, s, e);
        mstCost += b.cost;
    }
}

4. 모든 섬이 연결되었는지 확인

루트로 설정할 섬을 하나 정해서 설정한 뒤, Union Find의 Find를 돌려주면 된다.

int root = find(parent, 1);

for (int i = 2; i < islandCnt + 1; i ++) {
    if (find(parent, i) != root) {
        System.out.println(-1);
        return;
    }
}

전체 코드

public class Main {

    public static class Bridge {

        int start;
        int end;
        int cost;

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

    }

    private static int[] dx = { -1, 1, 0, 0 };
    private static int[] dy = { 0, 0, -1, 1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] 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());
            }
        }

        int islandCnt = 0;
        int[][] islandsMap = new int[N][M];
        boolean[][] isVisit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1 && !isVisit[i][j]) {
                    islandCnt++;
                    bfs(map, islandsMap, isVisit, N, M, i, j, islandCnt);
                }
            }
        }

        List<Bridge> bridges = findBridges(map, islandsMap, N, M);

        Collections.sort(bridges, (o1, o2) -> o1.cost - o2.cost);

        int[] parent = new int[islandCnt + 1];

        for (int i = 0; i < islandCnt + 1; i++) {
            parent[i] = i;
        }

        int mstCost = 0;

        for (Bridge b : bridges) {
            int s = b.start;
            int e = b.end;

            if (find(parent, s) != find(parent, e)) {
                union(parent, s, e);
                mstCost += b.cost;
            }
        }

        int root = find(parent, 1);

        for (int i = 2; i < islandCnt + 1; i ++) {
            if (find(parent, i) != root) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(mstCost);

    }

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

        return parent[x] = find(parent, parent[x]);
    }

    private static void union(int[] parent, int x, int y) {
        x = find(parent, x);
        y = find(parent, y);

        if (x == y)
            return;

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

    private static List<Bridge> findBridges(int[][] map,
            int[][] islandsMap, int N, int M) {
        List<Bridge> bridges = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //1. 섬이 있을 경우에만 탐색
                if (islandsMap[i][j] > 0) {
                    int number = islandsMap[i][j];

                    //2. bfs와 유사하게 직선 방향으로만 탐색
                    for (int k = 0; k < 4; k++) {
                        int length = 0;
                        int x = i;
                        int y = j;

                        while (true) {
                            x += dx[k];
                            y += dy[k];

                            //아래의 경우 탐색하지 않는다
                            //  3. 같은 정점(섬 그룹)에 속하거나
                            //  4. 길이가 1인 다른 섬의 경우
                            if (!isAvailableIdx(x, y, N, M) || islandsMap[x][y] == number
                                    || (length <= 1 && map[x][y] == 1))
                                break;

                            if (islandsMap[x][y] > 0 && length >= 2) {
                                bridges.add(new Bridge(number, islandsMap[x][y], length));
                                break;
                            }
                            length++;
                        }
                    }
                }
            }
        }

        return bridges;
    }

    private static void bfs(int[][] map, int[][] islandsMap,
    		boolean[][] isVisit, int N, int M, int x, int y, int cnt) {
        isVisit[x][y] = true;
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[] { x, y });
        islandsMap[x][y] = cnt;

        while (!que.isEmpty()) {
            int[] cur = que.poll();

            for (int i = 0; i < 4; i++) {
                int newX = cur[0] + dx[i];
                int newY = cur[1] + dy[i];

                if (isAvailableIdx(newX, newY, N, M) && !isVisit[newX][newY] && map[newX][newY] == 1) {
                    isVisit[newX][newY] = true;
                    islandsMap[newX][newY] = cnt;
                    que.offer(new int[] { newX, newY });
                }

            }
        }
    }

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

}

728x90