[백준, BOJ 17472] 다리 만들기 2 (java)

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

17472번: 다리 만들기 2

---

문제

섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.

다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.

섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다. 

아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.

다음은 올바르지 않은 3가지 방법이다

다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.

나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

출력

모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

728x90

 

예제 입력 1

7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

예제 출력 1

9

 

예제 입력 2

7 8
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1

예제 출력 2

10

 

예제 입력 3

7 8
1 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 1
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0

예제 출력 3

9

 

예제 입력 4

7 7
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1

예제 출력 4

-1

---

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

public class Main {
	
	static int N;
	static int M;
	static int[][] tmpMap;
	static int[][] map;
	static int num;
	static ArrayList<ArrayList<Integer>> bridgeList;
	static int visited;
	static int[] parent;
	static int result = 0;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// 입력
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		tmpMap = new int[N][M]; // 땅의 정보를 tmpMap에 저장한다
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				tmpMap[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 각 섬을 찾아 번호 매기기
		map = new int[N][M];
		findIsland();
		num--; // num은 섬의 개수
		
		// 각 섬에서 다른 섬으로 갈 수 있는 다리 구하기
		bridgeList = new ArrayList<>();
		for (int i = 0; i <= num; i++) {
			bridgeList.add(new ArrayList<>());
			for (int j = 0; j <= num; j++) {
				bridgeList.get(i).add(10);
			}
		}
		getBridge();
		
		// 각 섬에서 놓을 수 있는 다리 중 최소 길이 구하기
		visited = 0;
		getMin();
		
		// 출력
		for (int i = 1; i <= num; i++) find(i);
		boolean isTrue = true;
		for (int i = 1; i <= num; i++) {
			if(parent[i] != 1) {
				isTrue = false;
				break;
			}
		}
		if(!isTrue) System.out.println(-1);
		else System.out.println(result);
	}
	
	private static void findIsland() { // 섬을 찾아 각 섬에 번호를 메겨줌
		num = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(tmpMap[i][j] == 1) {
					dfs(i, j);
					num++;
				}
			}
		}
	}
	
	private static void dfs(int x, int y) { // 섬에 번호를 매길 때 사용할 dfs
		
		tmpMap[x][y] = 0; // 방문했다고 체크
		map[x][y] = num; // 번호 매김
		
		// 상하좌우
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		
		for (int i = 0; i < 4; i++) { // 사방탐색
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && nx < N && ny >= 0 && ny < M) { // 범위 체크
				if(tmpMap[nx][ny] == 1) dfs(nx, ny); // 사방에 이어진 땅이 있다면 dfs
			}
		}
	}

	private static void getBridge() { // 다리 구하기
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] != 0) { // 해당 칸이 섬이라면
					makeBirdge(i, j); // 해당 칸에서 다른 섬에 다리를 놓을 수 있는지 체크
				}
			}
		}
	}
	
	private static void makeBirdge(int x, int y) { // 해당 칸에서 다른 섬에 다리를 놓을 수 있는지 체크하는 메소드
		
		int numberOfIsland = map[x][y]; // 섬의 번호
		
		// 상하좌우
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};
		
		for (int i = 0; i < 4; i++) { // 사방탐색
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && nx < N && ny >= 0 && ny < M) { // 범위 체크
				if(map[nx][ny] == 0) { // map[x][y]가 섬의 가장자리 부분이었다면
					
					if(i == 0 || i == 1) { // 위, 아래쪽으로 놓을 수 있는 다리가 있는지 체크
						int tmpX = nx;
						while(tmpX >= 0 && tmpX < N && map[tmpX][y] == 0) tmpX += dx[i];
						if(tmpX >= 0 && tmpX < N && Math.abs(x - tmpX) - 1 >= 2 && map[tmpX][y] != numberOfIsland) { // 놓을 수 있는 경우
							int number = map[tmpX][y]; // 다리를 놓을 섬의 번호
							ArrayList<Integer> tmpList = bridgeList.get(numberOfIsland); // 현재 섬에서 놓을 수 있는 다리 정보 리스트 가져오기
							tmpList.set(number, Math.min(tmpList.get(number), Math.abs(x - tmpX) - 1)); // 현재 섬에서 tmpX에 해당하는 섬까지 놓을 수 있는 다리 길이 중 최소값 저장
						}
					}
					
					else { // 왼쪽, 오른쪽으로 놓을 수 있는 다리가 있는지 체크
						int tmpY = ny;
						while(tmpY >= 0 && tmpY < M && map[x][tmpY] == 0) tmpY += dy[i];
						if(tmpY >= 0 && tmpY < M && Math.abs(y - tmpY) - 1 >= 2 && map[x][tmpY] != numberOfIsland) { // 놓을 수 있는 경우
							int number = map[x][tmpY]; // 다리를 놓을 섬의 번호
							ArrayList<Integer> tmpList = bridgeList.get(numberOfIsland); // 현재 섬에서 놓을 수 있는 다리 정보 리스트 가져오기
							tmpList.set(number, Math.min(tmpList.get(number), Math.abs(y - tmpY) - 1)); // 현재 섬에서 tmpY에 해당하는 섬까지 놓을 수 있는 다리 길이 중 최소값 저장
						}
					}
				}
			}
		}
	}
	
	private static void getMin() { // 가능한 다리의 최소값 구하는 메소드
		
		parent = new int[num + 1];
		for (int i = 1; i <= num; i++) {
			parent[i] = i;
		}
		
		int dis = 2;
		while(dis <= 8) {
			for (int i = 1; i <= num; i++) {
				ArrayList<Integer> list = bridgeList.get(i);
				for (int j = 1; j <= num; j++) {
					// i, j 섬이 연결되지 않았다면
					if(list.get(j) == dis && !union(i, j)) {
						result += dis;
					}
				}
			}
			dis++;
		}
	}
	
	private static boolean union(int p1, int p2) {
		p1 = find(p1);
		p2 = find(p2);
		
		if(p1 == p2) return true;
		else {
			if(p1 < p2) parent[p2] = p1;
			else parent[p1] = p2;
			return false;
		}
	}
	
	private static int find(int p) {
		if(parent[p] == p) return p;
		else return parent[p] = find(parent[p]);
	}
}