[BOJ/Java] 17472. 다리 만들기 2

[BOJ/Java] 17472. 다리 만들기 2

17472번: 다리 만들기 2

---

문제 해석

'다리 만들기 2' 문제는 지도에서 여러 섬들을 최소 비용의 다리로 연결하여 모든 섬이 연결되도록 하는 최소 스패닝 트리를 구하는 문제다. 각 칸은 바다 또는 섬으로 표시되며, 다리는 바다 위에만 세울 수 있고, 다리의 길이는 2 이상이어야 하며 직선으로만 연결 가능하다. 이 문제를 풀기 위해 그래프의 최소 스패닝 트리를 구하는 크루스칼 알고리즘을 사용한다.

풀이 과정

1. 섬 구분: 입력된 지도에서 BFS를 사용하여 각 섬에 고유 번호를 부여한다.
2. 다리 연결 경로 탐색: 각 섬의 가장자리에서 다른 섬까지 도달할 수 있는 최소 다리 길이를 DFS를 통해 탐색하고, 이를 가중치로 가진 간선으로 저장한다.
3. 크루스칼 알고리즘 실행: 모든 간선을 가중치에 따라 정렬한 후, 사이클을 형성하지 않는 간선만 선택하여 최소 스패닝 트리를 구성한다.

코드

package edu.ssafy.im.BOJ.Gold.G1.No17472;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		new Main().io();
	}

	private int n;
	private int m;
	private int[][] map;
	private static final int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	private int depth;
	private ArrayList<Edge> edgeList;
	private int[][] weight;
	private int[] set;
	
	private void io() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 0) map[i][j] = -1;  // 바다는 -1로 표시
				if(map[i][j] == 1) map[i][j] = -2;  // 섬은 초기에 -2로 표시
			}
		}

		sb.append(sol());
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private int sol() {
		setBoundary(); // 섬 구분해주기
		findPath(); // 가능한 다리 찾기
		return kruskal(); // 최소 스패닝 트리 구하기
	}
	
	private void setBoundary() { // 섬 구분은 BFS로 구현
		depth = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == -2) {
					bfs(i, j, depth++);  // 새 섬 발견 시 BFS로 번호 부여
				}
			}
		}
	}
	
	private void bfs(int x, int y, int depth) { // BFS로 섬 구분
		Queue<Point> queue = new ArrayDeque<>();
		queue.offer(new Point(x, y));
		map[x][y] = depth;
		
		while (!queue.isEmpty()) {
			Point p = queue.poll();
			for (int d = 0; d < direction.length; d++) {
				int nx = p.x + direction[d][0];
				int ny = p.y + direction[d][1];
				
				if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
				if (map[nx][ny] != -2) continue;
				
				map[nx][ny] = depth;
				queue.offer(new Point(nx, ny));
			}
		}
	}
	
	private void findPath() { // 다리 연결 경로 찾기
		edgeList = new ArrayList<Edge>();
		weight = new int[depth][depth];  // 섬 사이의 최소 거리를 저장할 2차원 배열
		
		for (int i = 0; i < depth; i++) {
			for (int j = 0; j < depth; j++) {
				weight[i][j] = Integer.MAX_VALUE;  // 초기 거리를 무한대로 설정
			}
		}
		
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < m; y++) {
				if (map[x][y] != -1) {
					int from = map[x][y];
					for (int d = 0; d < direction.length; d++) {
						int nx = x + direction[d][0];
						int ny = y + direction[d][1];
						
						if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
						if (map[nx][ny] == map[x][y]) continue; // 같은 섬일 경우 생략
						
						dfs(nx, ny, d, 0, from);  // 다리 탐색을 위한 DFS
					}
				}
			}
		}
		
		for (int i = 0; i < weight.length; i++) { // 가중치 배열에서 가능한 모든 간선 추가
			for (int j = 0; j < weight.length; j++) {
				if (weight[i][j] != Integer.MAX_VALUE) {
					edgeList.add(new Edge(i, j, weight[i][j]));
				}
			}
		}
	}
	
	private void dfs(int x, int y, int d, int w, int from) { // DFS로 다리 건설 가능성 탐색
		if (map[x][y] != -1) { // 새로운 섬에 도달했을 때
			if (w > 1) { // 다리 길이는 2 이상이어야 함
				int to = map[x][y];
				if(w < weight[from][to]) { // 더 짧은 다리를 찾았다면 갱신
					weight[from][to] = w;
				}
			}
			return;
		}
		
		int nx = x + direction[d][0];
		int ny = y + direction[d][1];
		
		if (nx < 0 || ny < 0 || nx >= n || ny >= m) return;
		
		dfs(nx, ny, d, w+1, from);  // 계속해서 다리를 연장하며 탐색
	}
	
	private int kruskal() { // 크루스칼 알고리즘을 이용한 최소 스패닝 트리 구현
		makeSet();
		
		int weight = 0;
		int cnt = 0;
		Collections.sort(edgeList);  // 모든 간선에 대해 가중치 순으로 정렬
		for (Edge edge: edgeList) {
			if(!unionSet(edge.from, edge.to)) continue;  // 사이클이 형성되지 않도록 간선 선택
			weight += edge.weight;
			if(++cnt == depth-1) return weight;  // 모든 섬이 연결되면 종료
		}
		
		return -1; // 모든 섬을 연결할 수 없는 경우
	}
	
	private void makeSet() { // 각 정점을 독립적인 집합으로 초기화
		set = new int[depth];
		for (int i = 0; i < depth; i++) {
			set[i] = i;
		}
	}
	
	private int findSet(int org) { // 루트 노드 찾기
		if (set[org] == org) return org;
		else return set[org] = findSet(set[org]);  // 경로 압축
	}
	
	private boolean unionSet(int a, int b) { // 두 노드를 연결
		int c = findSet(a);
		int d = findSet(b);
		
		if (c == d) return false;
		
		set[c] = d;
		return true;
	}

	class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	
	class Edge implements Comparable<Edge>{
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return this.weight - o.weight;
		}
	}
}

시간 복잡도 분석

이 코드는 크루스칼 알고리즘과 BFS, DFS를 활용한다. 크루스칼 알고리즘의 시간 복잡도는 𝑂(𝐸log⁡𝐸)다. 여기서 𝐸는 간선의 수다. 섬의 구분과 다리 탐색을 위한 BFS와 DFS는 각각 𝑂(𝑁𝑀)의 시간이 소요된다. 여기서 𝑁과 𝑀은 지도의 세로 및 가로 크기다.

느낀점

이 문제를 통해 그래프 알고리즘의 중요성과 효율적인 탐색 방법에 대해 다시 한번 깊이 생각해 볼 수 있었다. 섬을 구분하고, 유효한 다리를 찾는 과정에서 다양한 알고리즘을 적절히 사용하는 것이 중요함을 느꼈다. 또한, 최소 스패닝 트리를 구현하는 크루스칼 알고리즘의 효율성과 그 구현에 있어서의 세심함이 중요하다는 점을 체감할 수 있었다.