• bfs로 각 섬을 라벨링
    • 땅을 의미하는 수를 1에서 -1로 변경
    • bfs 수행하면서 바다와 인접한 땅은 해당 방향과 함께 boundary list에 저장
  • 라벨링 후, boundary들로 간선(edge) 생성
    • 두 정점 사이에 여러 간선이 존재해도 모두 간선으로 생성
    • 당연히 모든 섬이 다 라벨링 후 edge를 생성해야 한다
  • prim 알고리즘을 통해 MST 구현
    • priority queue 이용, 간선이 여러 개 존재해도 가장 짧은 간선들로 연결됨


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150



import java.io.*;
import java.util.*;

public class Main {
	static final int MAX_K = 7;
	static final int LAND = -1;
	static final int SEA = 0;
	
	static int N, M, curLabel;
	static int[][] board;
	static List<Boundary> boundaryList;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = { 0,-1, 0, 1};

	static List<Node>[] edge = new ArrayList[MAX_K];
	static {
		for (int i = 0; i < MAX_K; i++)
			edge[i] = new ArrayList<>();
	}

	static class Boundary {
		int r, c, dir;
		Boundary(int r, int c, int dir) {
			this.r = r; this.c = c; this.dir =dir;
		}
	}

	static class Node implements Comparable<Node> {
		int to, dist;
		Node(int to, int dist) {
			this.to = to; this.dist = dist;
		}
		@Override
			public int compareTo(Node o) {
				return Integer.compare(this.dist, o.dist);
			}
	}

	static class Point {
		int r, c;
		Point(int r, int c) {
			this.r = r; this.c = c;
		}
	}

	static void bfs(int sr, int sc) {
		Queue<Point> q = new ArrayDeque<>();
		q.offer(new Point(sr, sc));
		board[sr][sc] = curLabel;
		while (!q.isEmpty()) {
			Point cur = q.poll();
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dx[i];
				int nc = cur.c + dy[i];
				if \(nr < 0 \|| nr >= N \|| nc < 0 \|| nc >= M)
					continue;

				if (board[nr][nc] == SEA)
					boundaryList.add(new Boundary(cur.r, cur.c, i));
				else if (board[nr][nc] == LAND) {
					board[nr][nc] = curLabel;
					q.offer(new Point(nr, nc));
				}
			}
		}
	}

	static void label() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == LAND) {
					curLabel++;
					bfs(i, j);
				}
			}
		}
	}

	static void makeEdge() {
		for (Boundary boundary : boundaryList) {
			int r = boundary.r;
			int c = boundary.c;
			int from = board[r][c];
			int dir = boundary.dir;

			int dist = 0;
			while (true) {
				r += dx[dir];
				c += dy[dir];
				if \(r < 0 \|| r >= N \|| c < 0 \|| c >= M) break;

				if (board[r][c] == SEA) {
					dist++;
					continue;
				}
				int to = board[r][c];
				if (from != to && dist >= 2)
					edge[from].add(new Node(to, dist));
				break;
			}
		}
	}

	static int prim() {
		int res = 0;
		boolean[] visited = new boolean[MAX_K];
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(1, 0));
		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			int from = cur.to;
			if (visited[from]) continue;
			visited[from] = true;
			res += cur.dist;

			for (int i = 0; i < edge[from].size(); i++)
				pq.offer(edge[from].get(i));
		}
		for (int i = 1; i <= curLabel; i++)
			if (!visited[i]) return -1;

		return res;
	}

	static int solution() {
		label();
		makeEdge();
		return prim();
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[N][M];
		boundaryList = new ArrayList<>();
		curLabel = 0;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if (board[i][j] == 1) board[i][j] = LAND;
			}
		}
		System.out.println(solution());
	}
}