백준 17472 - 다리 만들기 2

Java

17472 번 - 다리 만들기 2

문제

섬과 바다를 나타내는 지도의 정보가 주어진다.
다리를 연결해서 모든 섬을 연결하려고 한다.
최소한의 다리를 연결하여 모든 섬으로 이동 할 수 있게한다.

다리의 방향이 바뀌면 안된다.(직선만 가능)

접근 방법

1. 모든 섬끼리 잇는 거리를 2차원 배열로 저장한다.
   1-1. 섬을 구별해야 하므로, bfs로 각 섬마다 숫자를 부여하여 지도를 섬의 번호를 부여하여 갱신한다.
   1-2. 각 섬의 좌표를 2차원 ArrayList로 저장한다.
   1-3. 조합을 이용해 섬 2개 쌍(nC2)을 뽑는다. -> 섬끼리 (1,4) (4,1)와 같이 중복하여 닿지 않게 하기 위해
   1-4. 시작 섬의 좌표 중 하나씩 4방으로 탐색한다.
   1-5 만약 도착 섬에 도달하면, 그 거리의 최솟값을 2차원 배열의 값으로 넣는다.
   1-6. 섬 사이의 거리는 최소한 1은 넘어야하며, 중간에 목표 섬이 아닌 다른 섬을 만나면 중단

2. 저장된 거리 배열을 통해 MST를 만든다.

코드

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

public class Main {
	static int n, m, result;
	static boolean[][] vis;
	static int[][] map;
	static int[][] bridge;			// 섬끼리 다리를 이었을 때 그 길이를 담는 배열
	static int islandCnt = 0;
	static int sel[];
	static boolean vvis[];
	static List<List<Point>> island;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	
    	map = new int[n][m];
    	vis = new boolean[n][m];
    	island = new ArrayList<>();
    	island.add(new ArrayList<Point>());
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		for(int j = 0; j < m; j++) {
    			map[i][j] = stoi(stk.nextToken());
    		}
    	}
    	
		// 섬들의 번호를 부여한다.
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
    			if(!vis[i][j] && map[i][j] == 1)
    				bfs(i,j);
    		}
    	}
    	
		// 2개의 섬의 쌍을 가져온다.
    	sel = new int[2];
    	vvis = new boolean[islandCnt + 1];
    	bridge = new int[islandCnt + 1][islandCnt + 1];
    	dfs(0, 1);
    	
    	// 저장된 거리 배열을 통해 MST를 만든다.
    	int[] minEdge = new int[islandCnt + 1];
    	boolean[] visNode = new boolean[islandCnt + 1];
    	Arrays.fill(minEdge, Integer.MAX_VALUE);
    	minEdge[1] = 0;
    	int cnt = 0;
    	while(cnt < islandCnt) {
    		int min = Integer.MAX_VALUE;
    		int curVertex = 0;
    		for(int i = 1; i <= islandCnt; i++) {
    			if(!visNode[i] && min > minEdge[i]) {
    				min = minEdge[i];
    				curVertex = i;
    			}
    		}
    		
    		result += min;
    		visNode[curVertex] = true;
    		
    		for(int i = 1; i <= islandCnt; i++) {
    			if(!visNode[i] && minEdge[i] > bridge[curVertex][i] && bridge[curVertex][i] != 0) {
    				minEdge[i] = bridge[curVertex][i];
    			}
    		}
    		
    		cnt++;
    	}
    	for(int i = 1; i <= islandCnt; i++) {
    		if(!visNode[i]) {
    			System.out.println(-1);
    			br.close();
    			return;
    		}
    	}
    	System.out.println(result);
    	br.close();
	}
	
	// 조합을 이용해 섬 2개 쌍(nC2)을 뽑는다.
	private static void dfs(int lv, int start) {
		if(lv == 2) {
			//System.out.println(Arrays.toString(sel));
			makeBridge(sel[0],sel[1]);
			return;
		}
		for(int i = start; i <= islandCnt; i++) {
			if(!vvis[i]) {
				vvis[i] = true;
				sel[lv] = i;
				dfs(lv + 1, i + 1);
				vvis[i] = false;
			}
		}
	}
	
	private static void makeBridge(int start, int end) {
		
		int size = island.get(start).size();
		int bridgeLen = Integer.MAX_VALUE;
		int y, x, ny, nx, len;
		// 시작 섬의 좌표 중 하나씩 4방으로 탐색한다. 
		for(int idx = 0; idx < size; idx++) {
			Point curP = island.get(start).get(idx);
			y = curP.y;
			x = curP.x;
			
			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				
				len = 0;
				while(isIn(ny,nx) && map[ny][nx] == 0) {
					len++;
					ny += dy[i];
					nx += dx[i];
				}
				
				// 만약 도착 섬이랑 이어졌으면
				if(isIn(ny,nx) && map[ny][nx] == end) {
					if(len >= 2) {
						bridgeLen = Math.min(bridgeLen, len);
					}
				}
			}
		}
		
		if(bridgeLen != Integer.MAX_VALUE) {
			bridge[start][end] = bridgeLen;
			bridge[end][start] = bridgeLen;
		}
	}

	// 상 하 좌 우
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};

	// 섬을 구별해야 하므로, bfs로 각 섬마다 숫자를 부여한다.
	// 각 섬의 좌표를 2차원 ArrayList로 저장한다.
	static void bfs(int y, int x) {
		islandCnt++;
		island.add(new ArrayList<Point>());
		island.get(islandCnt).add(new Point(y,x));
		
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(y,x));
		vis[y][x] = true;
		map[y][x] = islandCnt;
		
		int ny, nx;
		while(!q.isEmpty()) {
			Point p = q.poll();
			y = p.y;
			x = p.x;
			
			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				
				if(isIn(ny,nx) && !vis[ny][nx] && map[ny][nx] == 1) {
					vis[ny][nx] = true;
					map[ny][nx] = islandCnt;
					island.get(islandCnt).add(new Point(ny,nx));
					q.add(new Point(ny,nx));
				}
			}
		}
		
	}
	
	public static class Point{
    	int y;
    	int x;
    	Point(int k,int v){
    		y = k;
    		x = v;
    	}
		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			builder.append("[").append(y).append(", ").append(x).append("]");
			return builder.toString();
		}	
    }
    // 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
    
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

DFS, BFS, MST을 다 쓰는 문제였다.

개선할 점

없습니다.