[BOJ] 다리 만들기 2

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

17472번: 다리 만들기 2

삼성 역량테스트 A형 (= 삼성 SW직군 공채 코딩테스트 수준) 기출 문제.

 

위 그림과 같은 맵이 주어지고, 파란색을 섬이라고 한다. 모든 섬을 연결할 수 있도록 다리 (회색) 를 놓아야 하는데 다리의 총 길이가 최소가 되도록 놓았을 때 그 길이를 구하는 문제이다.

 

> 다리는 가로 or 세로, 일직선으로만 놓아야 한다

> 두 섬을 잇기 위해 다리를 놓았는데 중간에 또다른 섬이랑 인접하더라도 그것은 연결된 것이 아니다 (그림의 D)

> 다리의 길이는 최소 2여야 한다 (길이 1짜리 다리는 놓을 수 없다)

> 다리가 교차할 수도 있으나 그 경우 교차하는 칸은 각 다리에서 모두 길이에 포함된다

 

입력은 아래와 같이 맵의 가로, 세로 길이와 맵의 상태 (0: 바다, 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

- 풀이:

각 섬을 정점 (vertex), 다리를 간선 (edge) 이라 생각하면 그래프로 볼 수 있으며, 모든 정점을 연결하면서 간선 비용의 합이 최소가 되는 것을 구하는 것이므로 MST (최소비용 신장트리) 문제이다.

다만 입력이 그래프 표현 형태로 주어지지 않으므로 주어지는 맵을 그래프로 변환하기 위한 전처리 작업이 필요하다.

 

1) 각 섬을 구별하기 위해 섬에 번호를 붙인다. - BFS/DFS

유명한 BFS/DFS 문제인 BOJ 2667 단지번호붙이기와 동일한 방법으로 하면 된다.

-> 각 섬 = 그래프의 정점이라 생각한다.

 

2) 모든 육지인 칸에 대하여, 바다를 향해 다리를 놓아보고 다른 섬에 닿는지 조사하고, 닿는 경우 그 길이를 저장한다. - 사방탐색, 완전탐색

-> 다리의 길이 = 섬과 섬을 잇는 간선의 길이라 생각한다.

 

3) 만들어진 정점과 간선 정보를 이용해 MST 알고리즘을 돌려 모든 섬을 잇는 최소비용을 구한다. - MST (프림/크루스칼 알고리즘)

 

- 코드 (Java):

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

// 간선 정보를 Priority Queue에 저장하기 위한 Edge 클래스
class Edge implements Comparable<Edge>{
	int start;
	int end;
	int cost;
	
	public Edge(int start, int end, int cost) {
		this.start = start;
		this.end = end;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) { // Priority Queue에서의 정렬기준 = cost
		return Integer.compare(this.cost, o.cost);
	}
}

public class boj_17472 {
	
	static int N, M;
	static int[][] map;
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {-1, 0, 1, 0};
	static PriorityQueue<Edge> pq;
	static int[] uf_parents;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		pq = new PriorityQueue<Edge>();
		
        // 크루스칼에서 사용하는 union-find 알고리즘을 위한 배열
		uf_parents = new int[8]; // 섬 최대 6개 -> 번호 최대 7번까지 가능

		for (int i=0; i<N; i++) {
			String line = bf.readLine();
			for (int j=0; j<M; j++) {
				map[i][j] = line.charAt(j*2) - '0';
			}
		} // 여기까지 입력
		
		// 섬번호 붙이기
		int island_num = 2; // 1은 이미 map에서 사용하고 있으므로 혼동 방지를 위해 2번부터
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if (map[i][j] == 1) {
					uf_parents[island_num] = -1;
					bfs(j, i, island_num++);
				}
			}
		}
		
		// 섬에 해당하는 모든 칸에서 가로나 세로로 이동해보면서 각 섬간의 거리 구하기
		for (int i=0; i<N; i++) {
			for (int j=0; j<M; j++) {
				if (map[i][j] != 0) {
					// 사방탐색
					for (int d=0; d<4; d++) {
						int nx = j + dx[d];
						int ny = i + dy[d];
                        // 다음 칸이 바다인 경우에만 다리 놓아보기 시도
						if (nx >= 0 && ny >= 0 && nx < M && ny < N && map[ny][nx] == 0) {
							getDist(j, i, map[i][j], dx[d], dy[d]);
						}
					}
					
				}
			}

		} 
		
		// 크루스칼 알고리즘
		int edgecount = 0;
		int ans = 0;
		boolean flag;
		while (edgecount < island_num-3) { // 섬개수 -1개의 edge 선택 (섬번호 2부터 시작하므로 -3)
			if (pq.isEmpty())
				break;
			
			Edge curEdge = pq.poll();
			flag = union(curEdge.start, curEdge.end); // 사이클 체크
			if (flag) {
				edgecount++;
				ans += curEdge.cost;
			}
		}
		
		// 섬개수 -1개의 edge를 선택하지 못하고 중간에 break 된 경우 모든 섬을 연결할 수 없다는 뜻
		if (edgecount < island_num-3)
			System.out.println(-1);
		else
			System.out.println(ans);
		
	}
	
    // 크루스칼 알고리즘에서 사이클 체크를 위한 union-find 알고리즘 파트
	private static boolean union(int a, int b) {
		int a_root = find_set(a);
		int b_root = find_set(b);
		if (a_root != b_root) {
			uf_parents[b_root] = a;
			return true;
		}
		else {
			return false;
		}
	}

	private static int find_set(int a) {
		if (uf_parents[a] == -1) {
			return a;
		}
		else {
			return uf_parents[a] = find_set(uf_parents[a]);
		}
	}

	// 다리 놓아보는 부분
	private static void getDist(int x, int y, int num, int dx, int dy) {
		
		int dist = 0;
		x += dx;
		y += dy;
		dist++;
		
		while (x >= 0 && y >= 0 && x < M && y < N) {
			if (map[y][x] != 0) { // 가로나 세로로 이동하다가, 다른 섬을 찾으면...
				if (dist > 2) { // dist=2는 길이 1짜리 다리인 경우임
					pq.add(new Edge(num, map[y][x], dist-1));
				}
				break;
			}
			
			x += dx;
			y += dy;
			dist++;
		}
		
	}

	// 섬 번호 붙이는 BFS
    // 맵에 번호가 새로 붙는 것 자체가 visited 표시. 따로 visited 배열은 필요없다
	private static void bfs(int x, int y, int num) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {x, y});
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			map[p[1]][p[0]] = num;

			for (int i=0; i<4; i++) {
				int nx = p[0] + dx[i];
				int ny = p[1] + dy[i];
						
				if (nx >= 0 && ny >= 0 && nx < M && ny < N && map[ny][nx] == 1) {
					q.offer(new int[] {nx, ny});
				}
			}
		}
	}
}

 

주의점:

1) 파트 - map에 이미 0, 1이 저장되어 있으므로 새로운 섬 번호는 2번부터 붙여야 한다는 점. (입력을 받을 때 1이 나올 때마다 1 말고 다른 번호로 바꿔버리는 방법도 있긴 하다)

2) 파트 - 길이 1짜리 다리는 허용되지 않는다는 점.

3) 파트 - (섬 개수 - 1) 개 만큼의 edge가 만들어지지 않는 경우가 있다는 점. -1을 출력하는 경우이다. 에러가 발생하지 않도록 PQ가 비는 경우엔 루프를 탈출시켜줘야 한다.

 

+ 2) 파트에서 같은 정점 쌍을 잇는 edge가 중복으로 PQ에 들어갈 수 있으나, union-find에서 걸러지기 때문에 별로 상관없다.