[백준] 17472.다리 만들기 2 (java) / 크루스칼, Union-Find, DFS, BFS, 시뮬레이션

@ 크루스칼, Union-Find, DFS, BFS, 시뮬레이션 / 1h 30m

9월 삼성 SW 역량테스트 2번 문제

 

종이에 쓰는시간 30분을 포함해서 1시간만에 풀었는데 몇가지 실수해서 디버깅하느라 +30분 걸렸다.

다익스트라, DFS 등 여러 개념을 이용해서 풀 수 있는 좋은 문제인 것 같다. 약간 어려운 편.

 

 

문제 링크

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

17472번: 다리 만들기 2

 

구현 방법

1. 먼저 각 섬들에 단지번호붙이기 방법을 이용해서 번호를 붙여준다.

(BFS, DFS 어떤 방식이든 상관없다)

이 때 섬에 해당하는 부분들을 Queue에 미리 넣어주면 나중에 다리를 그릴 때 굳이 2중for문으로 맵 전체를 탐색할 필요가 없어진다.

 

2. 1번에서 큐에 넣어놓은 값들로부터 4방탐색으로 다리를 그을 수 있는지 확인하고, 가능한 경우 다리를 만든다.

(이때 맵에 다리를 표시 할 필요는 없음)

그리고 우선순위 큐에 (출발섬번호, 도착섬번호, 길이) 정보를 넣어준다.

이 우선순위 큐는 길이가 작은 순으로 나오게 세팅해준다.

 

3. pq에서 뺀 순서대로 union-find를 돌린다.

 

 

 

풀고 나서 코드 리뷰를 받고, 다시 고쳐서 풀었다. 훨씬 간결해졌고 불필요한 부분이 없어졌다!

1. 기존 내 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	private static class Node implements Comparable<Node> {
		int x, y, val;
		Node (int x, int y, int val) {
			this.x = x;
			this.y = y;
			this.val = val;
		}
		@Override
		public int compareTo(Node o) {
			return this.val - o.val;
		}
	}

	private static int N, M, map[][], parents[], lenSum, islandNum;
	private static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
	private static Queue<Node> q;
	private static PriorityQueue<Node> pq;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		q = new LinkedList<>();
		pq = new PriorityQueue<>();
		
		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] == 1) map[i][j] = -1;
			}
		}
		
		findStart();
		startBridge();
		
		parents = new int[islandNum - 1];
		Arrays.fill(parents, -1);
		bridegeUnion();
		
		if (allBridegeUnionCheck())
			System.out.println(lenSum);
		else
			System.out.println("-1");
	}

	private static boolean allBridegeUnionCheck() {
		int num = 0;
		for (int i = 0; i < parents.length; i++)
			if (parents[i] < 0) num++;
		
		if (num == 1) return true;
		else return false;
	}

	private static void bridegeUnion() {
		while (!pq.isEmpty()) {
			Node temp = pq.poll();
			if (union(temp.x - 1, temp.y - 1))
				lenSum += temp.val;
		}
	}

	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if (aRoot != bRoot) {
			parents[bRoot] = aRoot;
			return true;
		}
		return false;
	}

	private static int find(int a) {
		if (parents[a] < 0)
			return a;
		return parents[a] = find(parents[a]);
	}

	private static void startBridge() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] != 0) {
					if (i > 0 && map[i - 1][j] == 0) oneBridge(i, j, 0, map[i][j]);
					if (i < N - 1 && map[i + 1][j] == 0) oneBridge(i, j, 1, map[i][j]);
					if (j > 0 && map[i][j - 1] == 0) oneBridge(i, j, 2, map[i][j]);
					if (j < M - 1 && map[i][j + 1] == 0) oneBridge(i, j, 3, map[i][j]);
				}
			}
		}
	}

	private static void oneBridge(int x, int y, int d, int startNo) {
		int nx = x;
		int ny = y;
		
		while (true) {
			nx += dx[d];
			ny += dy[d];
			
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) return;
			if (map[nx][ny] == 0) {
				continue;
			} else {
				int len = 0;
				if (d == 0 || d == 1)  {
					if (Math.abs(nx - x) == 2) return;
					len = Math.abs(nx - x) - 1;
				} else {
					if (Math.abs(ny - y) == 2) return;
					len = Math.abs(ny - y) - 1;
				}
				
				pq.add(new Node(startNo, map[nx][ny], len));
				return;
			}
		}
	}

	private static void findStart() {
		int idx = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == -1) {
					map[i][j] = idx;
					q.add(new Node(i, j, idx));
					bfs();
					idx++;
				}
			}
		}
		islandNum = idx;
	}

	private static void bfs() {
		while (!q.isEmpty()) {
			Node temp = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = temp.x + dx[d];
				int ny = temp.y + dy[d];
				
				if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] != -1) continue;
				
				map[nx][ny] = temp.val;
				q.add(new Node(nx, ny, temp.val));
			}
		}
	}
}

 

 

2. 개선한 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	private static class Node implements Comparable<Node> {
		int x, y, val;
		Node (int x, int y, int val) {
			this.x = x;
			this.y = y;
			this.val = val;
		}
		@Override
		public int compareTo(Node o) {
			return this.val - o.val;
		}
	}

	private static int N, M, map[][], parents[], lenSum, islandNum = 1;
	private static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
	private static Queue<Node> q;
	private static PriorityQueue<Node> pq;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		q = new LinkedList<>();
		pq = new PriorityQueue<>();
		
		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] == 1) map[i][j] = -1;
			}
		}
		findStart();
		startBridge();
		
		parents = new int[islandNum - 1];
		Arrays.fill(parents, -1);
		bridegeUnion();
		
		if (allBridegeUnionCheck())
			System.out.println(lenSum);
		else
			System.out.println("-1");
	}

	private static boolean allBridegeUnionCheck() {
		int num = 0;
		for (int i = 0; i < parents.length; i++)
			if (parents[i] < 0) num++;
		
		if (num == 1) return true;
		else return false;
	}

	private static void bridegeUnion() {
		while (!pq.isEmpty()) {
			Node temp = pq.poll();
			if (temp.val > 1 && union(temp.x - 1, temp.y - 1))
				lenSum += temp.val;
		}
	}

	private static boolean union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if (aRoot != bRoot) {
			parents[bRoot] = aRoot;
			return true;
		}
		return false;
	}

	private static int find(int a) {
		if (parents[a] < 0)
			return a;
		return parents[a] = find(parents[a]);
	}

	private static void startBridge() {
		while (!q.isEmpty()) {
			Node temp = q.poll();
			for (int d = 0; d < 4; d++)
				oneBridge(temp.x, temp.y, d, map[temp.x][temp.y]);
		}
	}

	private static void oneBridge(int x, int y, int d, int startNo) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		int len = 0;
		
		while (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] != startNo) {
			if (map[nx][ny] != 0) {
				pq.add(new Node(startNo, map[nx][ny], len));
				return;
			}
			nx += dx[d];
			ny += dy[d];
			len++;
		}
	}

	private static void findStart() {
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (map[i][j] == -1)
					dfs(i, j, islandNum++);
	}

	private static void dfs(int x, int y, int num) {
		map[x][y] = num;
		q.add(new Node(x, y, num));
		
		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M || map[nx][ny] != -1) continue;
			dfs(nx, ny, num);
		}
	}
}

맨 위가 개선한 코드, 3번째가 내가 푼 코드

 

삽질 포인트

1. 가로가 N, 세로가 M인데 M자리에 N을 썼다.. 잡는데 20분 걸림

이것때문에 계속 런타임에러 떴다..ㅎㅎ

 

2. 다리를 그리고 나면 반드시 return 해줘야 한다.

return문을 까먹어서 다리를 그리고 나서도 계속 코드가 돌아서 문제가 생겼다.

 

3. 섬이 직사각형이 아닐 수 있다.

문제에는 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고 라고 나와있는데, 이건 직사각형이 아닐 수도 있다는 뜻이다.

테케에는 직사각형만 들어가 있어서 직사각형이 아닐 수도 있다는 생각을 못했다.

그래서 처음에 섬1-섬4 사이에 다리가 그려지면 그 이후에는 그리지 않도록 visit 체크를 해서 틀렸다.

 

섬이 직사각형이 아니면, 섬1-섬4 사이의 다리의 길이가 각각 다를 수도 있기 때문에 visit 체크를 하면 안된다.

그냥 무조건 다리를 그을수 있으면 다 pq에 넣어주면 된다. 중복되는 다리는 어차피 union-find에서 걸러진다.

 

 

 

엄청 어려운 문제는 아니었는데, 몇개를 놓쳐서 계속 틀려서 힘들었다.

끝!