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

BFS + MST

📑 문제

백준 17472 다리 만들기 2

 

---

🌱 아이디어

BFS로 각 섬에 번호를 부여하고, 모든 섬을 연결하는 다리잇기(MST)로 구현하자

 

2차원 평면 상 섬과 바다가 입력으로 주어지고, 다리를 연결해서 모든 섬을 연결하려고 한다.

다리는 가장 짧게 연결해야 한다. 즉 모든 섬을 최소비용으로 모두 잇는다면 = 최소스패닝임을 유추해야 풀 수 있다.

 

아래와 같은 3단계를 거쳐서 구현했다.

 

1. 모든 섬을 탐색하고 번호를 부여한다 그래야 A -> B를 특정할 수 있다.

2. A -> B가 직선으로 장애물 없이 다리를 이을 수 있는지 판단 후 우선순위큐에 시작노드, 목표노드, 비용을 입력하기

3. 크루스칼알고리즘으로 모든 섬을 잇기

 

맵의 크기, 섬의 개수가 매우 작다, 시간초과를 걱정하는 것보다 차근차근 구현에 집중하는 게 좋은 문제인 것 같다!

---

🌱 코드 및 풀이

	public class Main {
	public static int N, M;
	public static int[] parent;
	public static int[][] arr1;
	public static boolean[][] vi;
	public static int[] dx = {0, 0, -1, 1};
	public static int[] dy = {-1, 1, 0, 0};
	public static PriorityQueue<mstNode> pq = new PriorityQueue<>();
	public static class node {
	int x, y;
	public node(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	// MST에 사용할 클래스
	public static class mstNode implements Comparable<mstNode> {
	int x, y, w;
	public mstNode(int x, int y, int w) {
	this.x = x;
	this.y = y;
	this.w = w;
	}
	@Override
	public int compareTo(mstNode o) {
	return w - o.w;
	}
	}
	// 부모 찾기
	public static int find(int x) {
	if (parent[x] == x) return x;
	return parent[x] = find(parent[x]);
	}
	// 집합 합치기
	public static boolean union(int x, int y) {
	int from = find(x);
	int to = find(y);
	if (from != to) {
	parent[to] = from;
	return false;
	}
	return true;
	}
	// 섬들 사이 다리 잇기
	public static void makeBridge(int x, int y) {
	int nowIsland = arr1[y][x];
	for (int i = 0; i < 4; i++) {
	int cnt = 0;
	for (int j = 1; j <= 10; j++) {
	int nx = x + j * dx[i];
	int ny = y + j * dy[i];
	if (nx < 0 || nx >= M || ny < 0 || ny >= N) break;
	int endIsland = arr1[ny][nx];
	if (nowIsland == endIsland) break; // 같은 섬끼리 충돌시 break;
	if (arr1[ny][nx] == 0) { // 바다라면 카운팅
	cnt++;
	} else { // 다른섬 도착시
	if (cnt >= 2) { // 다리의 길이가 2 이상일때 우선순위 큐 입력
	pq.offer(new mstNode(nowIsland, endIsland, cnt));
	}
	break;
	}
	}
	}
	}
	// 섬에 번호 부여하기
	public static void bfs(int x, int y, int flagN) {
	Queue<node> qu = new LinkedList<>();
	qu.offer(new node(x, y));
	vi[y][x] = true;
	arr1[y][x] = flagN;
	while (!qu.isEmpty()) {
	node nd = qu.poll();
	for (int i = 0; i < 4; i++) {
	int nx = nd.x + dx[i];
	int ny = nd.y + dy[i];
	if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
	if (!vi[ny][nx] && arr1[ny][nx] == 1) {
	vi[ny][nx] = true;
	arr1[ny][nx] = flagN; // 번호 넣기
	qu.offer(new node(nx, ny));
	}
	}
	}
	}
	public static void main(String[] args) throws IOException {
	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());
	int cnt = 0;
	arr1 = new int[N][M];
	parent = new int[7];
	vi = new boolean[N][M];
	for (int i = 0; i < 7; i++) {
	parent[i] = i;
	}
	for (int i = 0; i < N; i++) {
	st = new StringTokenizer(br.readLine());
	for (int j = 0; j < M; j++) {
	arr1[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	// 섬마다 번호 부여
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (!vi[i][j] && arr1[i][j] == 1) {
	bfs(j, i, ++cnt);
	}
	}
	}
	// 섬과 섬 사이 일직선으로 다리 잇기
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if (arr1[i][j] != 0) {
	makeBridge(j, i);
	}
	}
	}
	// 크루스칼 알고리즘으로 섬 잇기
	int answer = 0;
	int cntIsland = 1;
	while (!pq.isEmpty()) {
	mstNode now = pq.poll();
	if (!union(now.x, now.y)) {
	cntIsland++;
	answer += now.w;
	}
	}
	// 모든 섬을 이었다면 출력
	System.out.println(cnt == cntIsland ? answer : -1);
	}
	}

view raw 다리 만들기2.java hosted with ❤ by GitHub

---

🌱 느낀 점

4년전 최고기록 방 빼버렸습니다 헉;;

 

MST + BFS 구현문제라서 차근차근 풀었더니 1트 만에 자바 8 기준 1등 먹었네요 맛있습니다 ㅎㅎ

성능도 같이 생각하면서 알고리즘 코딩하는 게 습관이 된듯한 느낌이네요^^