공부 기록

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하는 문제이다.

=> 최소비용신장트리 중 Prim 알고리즘 사용

최소비용신장트리:

2020/07/19 - [알고리즘 공부/boj] - boj 1197: 최소 스패닝 트리

import java.util.*;
class Solution {
	public int solution(int v, int[][] costs) {
		LinkedList<Edge>[] pair = new LinkedList[v + 1];
		HashSet<Integer> vSet = new HashSet<Integer>();
		for (int i = 0; i < v; i++) {
			pair[i] = new LinkedList<Edge>();
			vSet.add(i);
		}

		for (int i = 0; i < costs.length; i++) {
			int start = costs[i][0];
			int end = costs[i][1];
			long cost = costs[i][2];

			pair[start].add(new Edge(end, cost));
			pair[end].add(new Edge(start, cost));
		}

		int currentNode = 1;
		int answer = 0;
		vSet.remove(1);

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.addAll(pair[currentNode]);

		while (!vSet.isEmpty()) {
			Edge minEdge = pq.poll();

			if (vSet.contains(minEdge.v)) {
				answer += minEdge.cost;
				currentNode = minEdge.v;
				vSet.remove(currentNode);
				pq.addAll(pair[currentNode]);
			}
		}
		return answer;
	}
}

class Edge implements Comparable<Edge> {
	int v;
	long cost;

	public Edge(int v, long cost) {
		this.v = v;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

칸의 높이차가 height 보다 큰 경우 사다리를 설치해야 하는데, 사다리 설치 비용은 두 칸의 높이차이다.

최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸을 방문 하도록 하는 문제이다.

역시나 사다리를 설치하는 모든 경우를 구하게 되면 시간초과가 날 것이므로 다른 방법을 사용해야 한다.

맨 처음에 든 생각은 사다리 설치 비용을 이분탐색으로 구해두고 모든 칸을 방문 가능한지 보면 되지 않나?였다.

하지만 이 경우 사다리 설치 비용을 구한다고 하더라도 사다리의 위치, 갯수 등을 정하는 것이 쉽지 않겠다는 생각이 들었다.

일단 문제에서 제공하는 예시를 보도록 하자.

예시 그림에서는 일단 구역 컬러링 하고 사다리를 최소한으로 배치했다.

따라서 예시 그림과 마찬가지로 가장 먼저 할 일은 bfs를 돌면서 사다리를 사용하지 않고 갈 수 있는 구역을 먼저 나누는 것이다. 

그 다음으로는 구역 간을 잇는 사다리를 한개씩 배치해 주면 된다.

사다리를 배치해 줄 때에는 인접한 위치 중에서,

구역간의 차이가 최소가 되는 한 개의 사다리를 골라야 한다.

즉, 위 문제는 구역을 나눈후 아래와 같이 최단 거리 문제로 변하게 된다.

import java.util.*;
class Solution {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public int solution(int[][] land, int height) {
		int length = land.length;
		int[][] colored = new int[length][length];

		int color = 1;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (colored[i][j] == 0) {
					colorLand(color++, colored, i, j, length, height, land);
				}
			}
		}

		int mat[][] = new int[color][color];
		HashSet<Integer> connections[] = new HashSet[color + 1];
		for (int i = 0; i < color; i++) {
			Arrays.fill(mat[i], Integer.MAX_VALUE);
			connections[i + 1] = new HashSet<Integer>();
		}

		minLadder(mat, colored, land, connections);

		return prim(mat, color, connections);
	}

	private int prim(int[][] mat, int length, HashSet<Integer> connections[]) {
		int sum = 0;

		PriorityQueue<Node> queue = new PriorityQueue<Node>();
		boolean[] isVisited = new boolean[length];

		queue.add(new Node(1, 0));

		while (!queue.isEmpty()) {
			Node node = queue.poll();

			if (!isVisited[node.name]) {
				isVisited[node.name] = true;
				sum += node.value;

				for (int next : connections[node.name]) {
					queue.add(new Node(next, mat[node.name][next]));
				}
			}
		}

		return sum;
	}

	private void minLadder(int mat[][], int colored[][], int land[][], HashSet<Integer> connections[]) {
		int length = colored.length;

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				for (int dir = 0; dir < 4; dir++) {
					int newRow = i + dr[dir];
					int newCol = j + dc[dir];

					if (isBoundary(newRow, newCol, length) && colored[i][j] != colored[newRow][newCol]) {
						int v1 = colored[i][j];
						int v2 = colored[newRow][newCol];
						int diff = Math.abs(land[i][j] - land[newRow][newCol]);

						mat[v1][v2] = Math.min(mat[v1][v2], diff);
						mat[v2][v1] = Math.min(mat[v2][v1], diff);

						connections[v1].add(v2);
						connections[v2].add(v1);
					}
				}
			}
		}
	}

	private void colorLand(int color, int colored[][], int row, int col, int length, int height, int land[][]) {
		colored[row][col] = color;

		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position position = queue.poll();
			colored[position.row][position.col] = color;

			for (int i = 0; i < 4; i++) {
				int newRow = position.row + dr[i];
				int newCol = position.col + dc[i];

				if (isBoundary(newRow, newCol, length) && colored[newRow][newCol] == 0 && Math.abs(land[position.row][position.col] - land[newRow][newCol]) <= height) {
					queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	private static boolean isBoundary(int row, int col, int length) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= length || col >= length) {
			return false;
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}

class Node implements Comparable<Node> {
	int name;
	int value;

	public Node(int name, int value) {
		this.name = name;
		this.value = value;
	}

	@Override
	public int compareTo(Node o) {
		return Integer.compare(this.value, o.value);
	}
}

정확성: 70.0

합계: 70.0 / 100.0

시간초과 & 메모리 초과 발생 -> prim말고 kruskal을 사용하도록 해보자.

kruskal은 좀 더 뭐랄까... 띄엄띄엄 이어져있는 그래프에서 유리하다고 한다.

import java.util.*;
class Solution {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public int solution(int[][] land, int height) {
		int length = land.length;
		int[][] colored = new int[length][length];

		int color = 1;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (colored[i][j] == 0) {
					colorLand(color++, colored, i, j, length, height, land);
				}
			}
		}

		PriorityQueue<Edge> queue = minLadderList(colored, land);

		return kruskal(queue, color);
	}

	private int kruskal(PriorityQueue<Edge> pq, int length) {
		int vSet[] = new int[length + 1];

		for (int i = 1; i <= length; i++) {
			vSet[i] = i;
		}

		int answer = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			answer += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				answer += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		return answer;
	}

	private PriorityQueue<Edge> minLadderList(int colored[][], int land[][]) {
		PriorityQueue<Edge> queue = new PriorityQueue<>();

		int length = colored.length;

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				for (int dir = 0; dir < 4; dir++) {
					int newRow = i + dr[dir];
					int newCol = j + dc[dir];

					if (isBoundary(newRow, newCol, length) && colored[i][j] != colored[newRow][newCol]) {
						int v1 = colored[i][j];
						int v2 = colored[newRow][newCol];
						int diff = Math.abs(land[i][j] - land[newRow][newCol]);

						queue.add(new Edge(v1, v2, diff));
					}
				}
			}
		}
		return queue;
	}

	private void colorLand(int color, int colored[][], int row, int col, int length, int height, int land[][]) {
		colored[row][col] = color;

		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position position = queue.poll();
			colored[position.row][position.col] = color;

			for (int i = 0; i < 4; i++) {
				int newRow = position.row + dr[i];
				int newCol = position.col + dc[i];

				if (isBoundary(newRow, newCol, length) && colored[newRow][newCol] == 0
						&& Math.abs(land[position.row][position.col] - land[newRow][newCol]) <= height) {
					queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	private static boolean isBoundary(int row, int col, int length) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= length || col >= length) {
			return false;
		}
		return true;
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

정확성: 93.3

합계: 93.3 / 100.0

결과는 메모리 초과는 넘어갔지만,, 테케 24, 25가 시간초과가 났다.

깨달은 점 - bfs를 돌 때는 Queue에 넣어줄 때 visited를 체크해야한다.

그렇지 않으면 중복되어서 들어가는 경우가 생길 수 있고, 그 때문에 시간 초과가 생길 수 있다.

최종 코드

import java.util.*;
class Solution {
	public static int dr[] = { 0, 0, 1, -1 };
	public static int dc[] = { 1, -1, 0, 0 };

	public int solution(int[][] land, int height) {
		int length = land.length;
		int[][] colored = new int[length][length];

		int color = 1;
		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				if (colored[i][j] == 0) {
					colorLand(color++, colored, i, j, length, height, land);
				}
			}
		}

		PriorityQueue<Edge> queue = minLadderList(colored, land);

		return kruskal(queue, color);
	}

	private int kruskal(PriorityQueue<Edge> pq, int length) {
		int vSet[] = new int[length + 1];

		for (int i = 1; i <= length; i++) {
			vSet[i] = i;
		}

		int answer = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			answer += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				answer += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		return answer;
	}

	private PriorityQueue<Edge> minLadderList(int colored[][], int land[][]) {
		PriorityQueue<Edge> queue = new PriorityQueue<>();

		int length = colored.length;

		for (int i = 0; i < length; i++) {
			for (int j = 0; j < length; j++) {
				for (int dir = 0; dir < 4; dir++) {
					int newRow = i + dr[dir];
					int newCol = j + dc[dir];

					if (isBoundary(newRow, newCol, length) && colored[i][j] != colored[newRow][newCol]) {
						int v1 = colored[i][j];
						int v2 = colored[newRow][newCol];
						int diff = Math.abs(land[i][j] - land[newRow][newCol]);

						queue.add(new Edge(v1, v2, diff));
					}
				}
			}
		}
		return queue;
	}

	private void colorLand(int color, int colored[][], int row, int col, int length, int height, int land[][]) {
		colored[row][col] = color;

		Queue<Position> queue = new LinkedList<Position>();
		queue.add(new Position(row, col));

		while (!queue.isEmpty()) {
			Position position = queue.poll();

			for (int i = 0; i < 4; i++) {
				int newRow = position.row + dr[i];
				int newCol = position.col + dc[i];

				if (isBoundary(newRow, newCol, length) && colored[newRow][newCol] == 0
						&& Math.abs(land[position.row][position.col] - land[newRow][newCol]) <= height) {
					colored[newRow][newCol] = color;
					queue.add(new Position(newRow, newCol));
				}
			}
		}
	}

	private static boolean isBoundary(int row, int col, int length) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= length || col >= length) {
			return false;
		}
		return true;
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Position {
	int row;
	int col;

	public Position(int row, int col) {
		this.row = row;
		this.col = col;
	}

	@Override
	public String toString() {
		return "(" + row + ", " + col + ")";
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

스패닝 트리: 그래프에서 일부 간선을 선택해서 만든 트리

최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치 합이 최소인 트리

스패닝 트리를 구하는 알고리즘

• Prim: 정점을 점점 확장해 나가는 방식 (힙을 써서 구현 - 정점번호, 가중치 저장) --> 최소값을 우선 순위 큐를 이용하면 최소 값을 logE만에 찾을 수 있다. 이 경우 시간복잡도는 O(ElogE)가 된다. 모든 간선이 힙에 한번 씩 들어갔다가 나오기 때문
  1. 그래프에서 아무 정점이나 선택한다.
  2. 선택한 정점과 선택하지 않은 정점을 연결하는 간선 중에 최소값을 고른다. 이 간선을 (u, v)라고 한다.
  3. 선택한 간선을 최소 스패닝 트리에 추가하고, 선택하지 않았던 정점 v를 선택한다.
  4. 2번으로 돌아간다

• Kruskal: 간선을 점점 확장해 나가는 방법
  1. 가중치가 작은 edge부터 살펴본다 --> 간선의 길이 순으로 먼저 정렬해야 한다. O(ElogE)
  2. edge e가 (u, v, c)일 때,  u와 v가 서로 다른 집합이면 e를 최소 스패닝 트리에 추가한다. O(E) - union/find 연산

Prim 알고리즘 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Edge>[] pair = new LinkedList[v + 1];
		HashSet<Integer> vSet = new HashSet<Integer>();
		for (int i = 1; i <= v; i++) {
			pair[i] = new LinkedList<Edge>();
			vSet.add(i);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pair[start].add(new Edge(end, cost));
			pair[end].add(new Edge(start, cost));
		}

		int currentNode = 1;
		long ans = 0;
		vSet.remove(1);

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		pq.addAll(pair[currentNode]);

		while (!vSet.isEmpty()) {
			Edge minEdge = pq.poll();

			if (vSet.contains(minEdge.v)) {
				ans += minEdge.cost;
				currentNode = minEdge.v;
				vSet.remove(currentNode);
				pq.addAll(pair[currentNode]);
			}
		}
		System.out.println(ans);
	}
}

class Edge implements Comparable<Edge> {
	int v;
	long cost;

	public Edge(int v, long cost) {
		this.v = v;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}

Kruskal 알고리즘 풀이

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		int vSet[] = new int[v + 1];

		for (int i = 1; i <= v; i++) {
			vSet[i] = i;
		}

		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long cost = in.nextLong();

			pq.add(new Edge(start, end, cost));
		}

		long ans = 0;
		if (!pq.isEmpty()) {
			Edge firstEdge = pq.poll();
			ans += firstEdge.cost;
			union(firstEdge.v1, firstEdge.v2, vSet);
		}

		while (!isFinished(vSet) && !pq.isEmpty()) {
			Edge minEdge = pq.poll();

			int v1Contains = find(minEdge.v1, vSet);
			int v2Contains = find(minEdge.v2, vSet);

			if (v1Contains != v2Contains) {
				ans += minEdge.cost;
				union(minEdge.v1, minEdge.v2, vSet);
			}
		}
		System.out.println(ans);
	}

	public static void union(int x, int y, int[] vSet) {
		int ux = find(x, vSet);
		int uy = find(y, vSet);

		vSet[uy] = ux;
	}

	public static int find(int x, int[] vSet) {
		if (vSet[x] == x) {
			return x;
		}

		vSet[x] = find(vSet[x], vSet);
		return vSet[x];
	}

	public static boolean isFinished(int[] vSet) {
		int now = vSet[1];
		for (int i = 1; i < vSet.length; i++) {
			if (vSet[i] != now) {
				return false;
			}
		}
		return true;
	}
}

class Edge implements Comparable<Edge> {
	int v1, v2;
	long cost;

	public Edge(int v1, int v2, long cost) {
		this.v1 = v1;
		this.v2 = v2;
		this.cost = cost;
	}

	@Override
	public int compareTo(Edge o) {
		return Long.compare(this.cost, o.cost);
	}
}