백준 17472 '다리 만들기 2'

Bonwoong Ku·2023년 10월 4일

BFS DFS MST ps 골드1 구현 그래프 백준

알고리즘 문제풀이

목록 보기

45/110

아이디어

1. 섬 번호 붙이기

맵 전체를 탐색하며 섬을 발견하면 사방 탐색으로 인접한 모든 섬 타일에 번호를 붙인다.
- DFS, BFS 중 DFS를 사용하였다.
이 섬 번호는 그래프에서 정점 번호로 사용한다.

2. 다리 연결 그래프 구성

맵 전체를 탐색하며 섬 타일이라면 4방향으로 다리를 뻗어본다.
- 다리가 같은 섬에 이어진다면 취소한다.
- 다리의 길이가 2보다 작다면 취소한다.
- 기존에 있던 다리보다 더 길다면 취소한다.
위 과정으로 섬을 정점, 다리를 간선으로 하는 가중치 그래프를 얻는다.

3. 최소 스패닝 트리

해당 그래프에 대해 최소 스패닝 트리의 총 길이를 구한다.
- 여기선 간단하게 $O(V^2)$ 인 Prim 알고리즘을 사용했다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tk = null;

    static int N, M, V, E, ans;
    static int[][] map;    // -1: 미결정, 0: 바다, 1 이상: 섬
    static int[][] graph;	// 다리 그래프 인접행렬
    
    // prim algorithm
    static int[] dist;
    static boolean[] visited;
    
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int INF = Integer.MAX_VALUE / 2;
    
    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        N = Integer.parseInt(tk.nextToken());
        M = Integer.parseInt(tk.nextToken());
        
        map = new int[N][M];
        for (int y=0; y<N; y++) {
            tk = new StringTokenizer(rd.readLine());
            for (int x=0; x<M; x++) {
                map[y][x] = tk.nextToken().charAt(0) == '1' ? -1 : 0;
            }
        }
        
        // map에 섬 번호 붙이기
        for (int y=0; y<N; y++) {
            for (int x=0; x<M; x++) {
                if (map[y][x] == -1) {
                    setIsland(y, x, ++V);
                }
            }
        }
        
        // V: 섬 개수
        
        // dist 초기화
        graph = new int[V+1][V+1];
        for (int i=1; i<=V; i++) {
            for (int j=1; j<=V; j++) {
                graph[i][j] = (i == j) ? 0 : INF;
            }
        }
        
        // 연결 확인
        for (int y=0; y<N; y++) {
            for (int x=0; x<M; x++) {
                int src = map[y][x];
                if (src <= 0) continue;
                for (int d=0; d<4; d++) {
                    int[] result = measure(y, x, d);
                    if (result == null)            continue;
                    int dest = result[0];
                    int len = result[1];
                    if (src == dest)            continue;
                    if (len < 2)                continue;
                    if (graph[src][dest] <= len) continue;
                    
                    if (graph[src][dest] == INF) E++;
                    graph[src][dest] = graph[dest][src] = len;
                }
            }
        }
        
        // E: 연결 가능한 다리 수

        // Prim - O(V^2)
        // 초기화
        dist = new int[V+1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        
        visited = new boolean[V+1];
        
        for (int i=1; i<=V; i++) {
            // 미선택 최소 가중치 간선 선택
            int minIdx = -1;
            int minDist = INF;
            for (int j=1; j<=V; j++) {
            	if (!visited[j] && dist[j] < minDist) {
            		minDist = dist[j];
            		minIdx = j;
            	}
            }
            
            if (minIdx == -1) {		// MST 구성 불가능
                System.out.println(-1);
                return;
            }
            
            visited[minIdx] = true;
            ans += minDist;
            for (int j=1; j<=V; j++) {
            	dist[j] = Math.min(dist[j], graph[minIdx][j]);
            }
        }
        
        System.out.println(ans);
        return;
    }
    
    // dfs
    static void setIsland(int y, int x, int idx) {
        map[y][x] = idx;
        for (int i=0; i<4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (map[ny][nx] != -1) continue;
            setIsland(ny, nx, idx);
        }
    }
    
    // 다리를 놓았을 떄의 길이와 연결된 섬 번호
    static int[] measure(int y, int x, int dir) {
        int cy = y;
        int cx = x;
        int d = 0;
        while (true) {
            cy += dy[dir];
            cx += dx[dir];
            if (cy < 0 || cy >= N || cx < 0 || cx >= M) return null;
            if (map[cy][cx] != 0) {
                return new int[] {map[cy][cx], d};
            }
            d++;
        }
    }
}