Algorithm
백준_다리만들기2_17472
Young_J
2020. 9. 4. 09:16
다리만들기 2
DFS 와 MST를 이용한 풀이.
DFS로 섬의 개수와 위치를 파악하고
크루스칼을 사용하여 풀이 하였음.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class 다리만들기2_17472 {
static int N, M, map[][], index = 2, parents[];
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };
static ArrayList<Point> list;
static class Point implements Comparable<Point> {
int from, to, cnt;
public Point(int from, int to, int cnt) {
super();
this.from = from;
this.to = to;
this.cnt = cnt;
}
@Override
public String toString() {
return "Point [from=" + from + ", to=" + to + ", cnt=" + cnt + "]";
}
@Override
public int compareTo(Point o) {
// TODO Auto-generated method stub
return Integer.compare(this.cnt, o.cnt);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
list = new ArrayList<Point>();
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());
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
if (map[r][c] == 1) {
map[r][c] = index;
dfs(r, c);
index++;
}
}
}
parents = new int[index];
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
if (map[r][c] == 0)
continue;
// 해당 좌표에서 상하좌우로 움직이면서 연결 할 수 있는 지점 찾기
check(r, c);
}
}
Collections.sort(list);
makeSet();
int Ans = 0;
int e = 0;
for (Point lists : list) {
if (e == index - 3)
break;
if (union(lists.from, lists.to)) {
e++;
Ans += lists.cnt;
}
}
if (e == index - 3) {
System.out.println(Ans);
} else {
System.out.println("-1");
}
// print(map);
// System.out.println(e);
// System.out.println(index);
// System.out.println(Ans);
// System.out.println(list.size());
}
private static boolean union(int x, int y) {
int xx = find(x);
int yy = find(y);
if (xx == yy)
return false;
parents[yy] = xx;
return true;
}
private static int find(int x) {
if (x == parents[x])
return x;
return parents[x] = find(parents[x]);
}
private static void makeSet() {
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
}
private static void check(int r, int c) {
// 상
cal(0, r, c);
// 하
cal(1, r, c);
// 좌
cal(2, r, c);
// 우
cal(3, r, c);
}
private static void cal(int i, int r, int c) {
int count = 0;
int nr = r;
int nc = c;
while (true) {
nr += dr[i];
nc += dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= M || map[nr][nc] == map[r][c])
break;
count++;
if (map[nr][nc] != 0) {
if (count > 2) {
list.add(new Point(map[r][c], map[nr][nc], count - 1));
}
break;
}
}
}
private static void dfs(int r, int c) {
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nc < 0 || nr >= N || nc >= M)
continue;
if (map[nr][nc] == 1) {
map[nr][nc] = index;
dfs(nr, nc);
}
}
}
private static void print(int[][] map) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
}