[Gold I] 다리 만들기 2 - 17472
성능 요약
메모리: 18436 KB, 시간: 188 ms
분류
너비 우선 탐색, 브루트포스 알고리즘, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 최소 스패닝 트리
제출 일자
2024년 8월 21일 23:10:33
문제 설명
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.
섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.
다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.
다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.
섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.
아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.
|
다리의 총 길이: 13 |
다음은 올바르지 않은 3가지 방법이다
| C의 방향이 중간에 바뀌었다 | D의 길이가 1이다. | 가로 다리인 A가 1과 가로로 연결되어 있지 않다. |
다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.
|
A의 길이는 4이고, B의 길이도 4이다. |
나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.
코드 풀이
class Edge를 만들고,from: 시작 vertex,to: 도착 vertex,weight: 다리 길이(가중치),hashCode(), equals():weight가 같은 edge 중복 제거하려고 작성(무향 그래프이기 때문에)HashSet<Edge>를 사용하여 중복없는Edge Set을 만들고,ArrayList<Edge>로 변환하여weight오름차순 정렬HashMap<Integer, Integer>를 사용하여Key: vertex,Value: parent 로 삽입Kruskal알고리즘을Union-find알고리즘을 이용하여 구현
작성한 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static class Edge {
int from, to;
int weight;
public Edge(int from, int to, int weight) {
super();
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public String toString() {
return "Edge [from=" + from + ", to=" + to + ", weight=" + weight + "]\n";
}
@Override
public int hashCode() {
return Objects.hash(weight);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Edge other = (Edge) obj;
return ((from == other.from && to == other.to) || (from == other.to && to == other.from))
&& weight == other.weight;
}
}
public static int M, N;
public static int map[][];
public static int visited[][];
public static Set<Edge> edges;
public static HashMap<Integer, Integer> parents;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
map = new int[M][N];
visited = new int[M][N];
edges = new HashSet<Edge>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int idx = 1;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
connect(i, j, idx++);
}
}
makeEdge();
List<Edge> edgeList = new ArrayList<Edge>(edges);
edgeList.sort((o1, o2) -> o1.weight - o2.weight);
parents = new HashMap<Integer, Integer>();
for (Edge e : edges) {
parents.putIfAbsent(e.from, e.from);
parents.putIfAbsent(e.to, e.to);
}
int w = kruskal(edgeList);
System.out.println(w);
}
public static void connect(int r, int c, int idx) {
if (map[r][c] == 0 || visited[r][c] != 0)
return;
visited[r][c] = idx;
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
for (int i = 0; i < 4; i++) {
if (0 <= r + dy[i] && r + dy[i] < M && 0 <= c + dx[i] && c + dx[i] < N) {
connect(r + dy[i], c + dx[i], idx);
}
}
}
public static void makeEdge() {
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] > 0) {
for (int k = 0; k < 4; k++) {
int r = i + dy[k];
int c = j + dx[k];
while (0 <= r && r < M && 0 <= c && c < N) {
if (visited[r][c] == visited[i][j]) {
break;
} else if (visited[r][c] == 0) {
r += dy[k];
c += dx[k];
} else {
int row = Math.abs(r - i) - 1;
int col = Math.abs(c - j) - 1;
int w = row > col ? row : col;
edges.add(new Edge(visited[i][j], visited[r][c], w));
break;
}
}
}
}
}
}
}
public static int findSet(int v) {
if (parents.get(v) == v)
return v;
int p = findSet(parents.get(v));
parents.put(v, p);
return p;
}
public static boolean union(int a, int b) {
int aParent = findSet(a);
int bParent = findSet(b);
if (aParent == bParent)
return false;
parents.put(aParent, bParent);
return true;
}
public static int kruskal(List<Edge> edgeList) {
int w = 0;
int cnt = 0;
for (Edge e : edgeList) {
if (e.weight >= 2 && union(e.from, e.to)) {
w += e.weight;
if (++cnt == parents.size() - 1)
break;
}
}
Set<Integer> tmpSet = parents.keySet();
Iterator<Integer> it = tmpSet.iterator();
int tmp = -1;
if (it.hasNext())
tmp = findSet(it.next());
while (it.hasNext()) {
if (tmp != findSet(it.next())) {
w = -1;
break;
}
}
if (w == 0)
w = -1;
return w;
}
}
곤듀님의 코드.. 알차게 훔쳐가겠습니다 슈슉 - 괴도L