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

 

 

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

17472번: 다리 만들기 2

 

문제

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

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

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

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

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

 

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

입력

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

출력

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

제한

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

---

# 접근

처음에 완전 탐색으로 백트래킹을 시도해 건설할 수 있는 모든 다리들을 연결하며 최소값을 갱신하려고 했으나 섬을 모두 연결만 하면 되기 때문에 최소 필요한 다리 개수인 섬의 수 -1개를 건설하면 되겠다고 생각했습니다. 그래서 자연스럽게 MST를 생각하게 되었고 MST를 구성하기 위한 가중치 값을 구하기 위해 dfs를 사용하기로 결정했습니다. 큰 로직은 섬을 구분하기 위해 bfs로 서로 인접해있는 섬에 넘버링을 한 후에 상하좌우 탐색을 하면서 dfs로 다리를 건설했습니다. 그리고 그때의 길이를 섬과 섬의 연결 관계, 가중치를 나타내는 간선 리스트에 담아 MST를 수행하기로 했습니다.

 

구현에 필요한 자료구조 및 변수들

• 초기 섬과 바다의 값을 담을 2차원 배열 : map[][]
• 다리의 생성 여부를 확인하기 위한 boolean 변수 : isEnd
• 섬에 넘버링을 하기 위해 수행할 bfs에서 방문 표시를 관리할 boolean 2차월 배열 : visited[][]
• 상하좌우 탐색을 위한 dx[], dy[]
• 간선 리스트를 구성하기 위한 ArrayList
• kruskal을 사용할 때 필요한 1차원 int형 배열 : parents[]

 

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

// 실행 시간 80ms
public class BOJ_17472_다리만들기2 {

	public static int N, M, num, island, result, parents[], map[][];
	public static boolean isEnd, visited[][];
	public static int dx[] = {-1, 1, 0, 0};
	public static int dy[] = {0, 0, -1, 1};
	public static ArrayList<Edge> list;

	// 섬에 번호를 붙이기 위한 bfs를 위한 Pair 클래스
	public static class Pair {
		int x, y;

		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	// 섬들의 간선 정보를 저장하기 위한 클래스
	public static class Edge {
		// 정점1과 정점2의 가중치 weight 표현
		int node1, node2, weight;

		public Edge(int node1, int node2, int weight) {
			this.node1 = node1;
			this.node2 = node2;
			this.weight = weight;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input[] = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);

		map = new int[N][M];
		visited = new boolean[N][M];

		// 입력값 받기
		for(int i = 0; i < N; i++) {
			input = br.readLine().split(" ");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}

		// 1. 섬에 넘버링 하기
		num = 1;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(!visited[i][j] && map[i][j] == 1){
					setNumber(i, j, num++); //bfs로 넘버링 수행
				}
			}
		}
		
		island = num;
		
		// 2. 다리 만들기
		list = new ArrayList<Edge>(); // 섬의 연결 정보를 저장하기 위한 리스트 생성
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] >= 1) { // 땅인 지점에서만 다리 만들기 시도
					num = map[i][j]; // 현재 처리하고 있는 섬의 번호 저장
					for(int d = 0; d < 4; d++) { // 상하좌우 갈 수 연결할 수 있는지 탐색
						isEnd = false; // dfs를 종료할 변수 false로 초기화
						// 다리를 만들고자 시도하는 곳이 범위를 넘어가는지 체크
						if(checkRange(i + dx[d], j + dy[d])) continue; 
						// 다리를 만들고자 하는 곳이 0인 경우에 다리 생성 가능
						if(map[i + dx[d]][j + dy[d]] == 0) {
							// dfs 수행
							makeBridge(i + dx[d], j + dy[d], d, 1);
						}
					}
				}
			}
		}
		
		// 3. MST 생성
		// 가중치를 기준으로 오름차순 정렬 수행
		Collections.sort(list, new Comparator<Edge>() {

			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.weight - o2.weight;
			}
		});
		
		// 부모 노드를 바로 알기 위한 배열 생성
		parents = new int[island + 1];
		
		// 본인을 부모 노드로 셋팅
		Arrays.fill(parents, -1);
		
		int cnt = 0;
		// 리스트에 담긴 연결 정보 하나씩 처리
		for(Edge edge : list) {
			// 정점 1과 정점 2를 합칠 수 있는지 즉, 이미 연결되어 있는지 확인
			if(union(edge.node1, edge.node2)) {
				// 합치는 것이 가능하다면 연결 가능한 것으로 연결 수행
				result += edge.weight;
				cnt++;
			}
			
			// 연결 수행 횟수가 정점 - 1개가 되면 MST 생성 완료
			if(cnt == island - 2) break;
		}
		
		// 간선의 수가 n - 1이 되지 않는다면 MST 생성 불가이므로 이를 만족하는 경우에만 최종 길이 출력
		System.out.println(cnt < island - 2 ? -1 : result);
	}

	private static void setNumber(int x, int y, int num) {
		Queue<Pair> q = new LinkedList<Pair>();
		map[x][y] = num;
		q.offer(new Pair(x, y));
		visited[x][y] = true;

		while(!q.isEmpty()) {
			Pair cur = q.poll();

			for(int d = 0; d < 4; d++) {
				int nx = cur.x + dx[d];
				int ny = cur.y + dy[d];

				if(checkRange(nx, ny)) continue;
				if(visited[nx][ny]) continue;
				if(map[nx][ny] == 1) {
					map[nx][ny] = num;
					q.add(new Pair(nx, ny));
					visited[nx][ny] = true;
				}
			}
		}
	}

	private static void makeBridge(int x, int y, int d, int dist) {
		// 범위 벗어나는지 체크
		if(checkRange(x, y)) {
			isEnd = true;
			return;
		}

		// 1보다 크다면 일단 섬이라는 의미
		if(map[x][y] >= 1) {
			// 그 중에서 다리를 건설하기 시작한 곳의 섬 번호와 다른 섬이고 다리 길이가 2이상인 경우 건설 가능
			if(map[x][y] != num && dist - 1 >= 2) {
				// 출발한 섬, 도착 섬, 이들의 다리 길이를 저장
				list.add(new Edge(num, map[x][y], dist - 1));
			} 
			// 1보다 큰 경우는 모두 다리 건설이 끝나는 경우이므로 flag값 변경
			isEnd = true;
			return;
		}

		// 계속 진행되어 왔던 방향으로 다리 건설 시도
		makeBridge(x + dx[d], y + dy[d], d, dist + 1);
		// dfs 수행 후 돌아와서 결과 값이 다리 건설이 종료되었다면 return
		if(isEnd) return;
	}
	
	private static boolean union(int x, int y) {
		int xRoot = find(x); // 정점 x의 부모 노드 반환
		int yRoot = find(y); // 정점 y의 부모 노드 반환
		
		// 둘의 부모가 같지 않다면 합치는 것 가능
		if(xRoot != yRoot) {
			parents[yRoot] = xRoot; // 편의상 yRoot를 xRoot로 변경(path compression)
			return true;
		}
		return false;
	}
	
	private static int find(int x) {
		// 0보다 작은 경우 부모 노드인 것이므로 x 반환
		if(parents[x] < 0) return x;
		// 아닌 경우 계속해서 부모를 찾기 위해 거슬러 올라감.
		return parents[x] = find(parents[x]);
	}

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

 

 

# 문제를 풀고 느낀 점

저는 개인적으로 이 문제는 매우 좋은 문제였다고 생각합니다. 다양한 기법과 알고리즘을 복합적으로 사용할 수 있고 대표적인 MST 문제 느낌이 아니었기 때문에 사고력을 확장하는 데 도움을 준 문제입니다. 

MST인 것을 빠르게 캐치하고 MST를 구성하기 위한 다리 건설(전처리)을 빠르게 했다면 목표 시간 안에 해결할 수 있는 문제인 것 같습니다.