🌉Solution & Idea
- 최소 비용으로 모든 다리를 연결한다는 점에서
kruskal algorithm을 떠올린다 - 각 섬에 번호를 매기고
vec이라는 이름의vector를 만들어{dist, 섬1, 섬2}를 저장한다. 이는섬1과 섬2간 거리는 dist라는 뜻이다 vec에 저장된 값을 참고로MST(Minimum Spannign Tree)를 만든다- 이렇게 만든
MST가 모든 섬을 연결하는지 확인한다
🌉1. Numbering - Init map
BFS를 이용하여 각 섬에 1번부터 번호를 매긴다- 한번도 방문된 적이 없고 현재 값이 1이면 (입력받을 때 모든 섬은 1로 입력 받는다), 현재 위치에서 인접한 모든 1 (같은 섬의 모든 좌표)에
numbering을 해줌
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (!visited[i][j] && map[i][j] == 1) {
visited[i][j] = true;
map[i][j] = num;
bfs(i, j, num);
num++;
}
}
}
num--;void bfs(int i, int j, int num) {
queue<pair<int, int> >q;
q.push(make_pair(i, j));
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny <= 0 || nx <= 0 || ny > N || nx > M) continue;
if (!visited[ny][nx] && map[ny][nx] == 1) {
map[ny][nx] = num;
visited[ny][nx] = true;
q.push(make_pair(ny, nx));
}
}
}
}🌉2. Check Distance
- 섬 간 다리를 놓을 수 있는 거리를 조사
- 다리는
세로 혹은 가로로만놓을 수 있기 때문에, 섬의 각 좌표에서 상하좌우로 움직이다가 다른 섬을 만났을 때 거리를vec에 저장 - 각 좌표에서 상하좌우로 움직이다가 범위를 벗어나거나 자신의 섬을 만나는 경우 바로 탐색을 종료한다
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (map[i][j] != 0)
check_dist(map[i][j], i, j);
}
}now는 현재 탐색하려는(y,x)가 위치한 섬의 번호vec에는{dist, 섬1, 섬2}가 저장되고 이는섬1과 섬2간 거리는 dist라는 뜻
(이때 dist를 먼저 저장하는 이유는 후에 오름차순으로 정렬을 해서 MST를 만들기 위해)
void check_dist(int now, int y, int x) {
for (int i = 0; i < 4; i++) {
int ny = y;
int nx = x;
int dist = 0;
while (true) {
ny += dy[i];
nx += dx[i];
if (ny <= 0 || nx <= 0 || ny > N || nx > M ||
map[ny][nx] == now) break;
if (map[ny][nx] != 0) {
vec.push_back(make_pair(make_pair(dist, now), map[ny][nx]));
break;
}
dist++;
}
}
}🌉3. Make MST
- 위에서 구한 vec를 오름차순 정렬을 한 뒤 MST를 만든다
sort(vec.begin(), vec.end());- 섬간 거리가 2이상이 아닌 경우는 넘어가고 두 섬을 합치는데 이미 합쳐져 있었던 경우 (크루스칼 알고리즘의 풀이에 의해 두 부모 섬이 같은 경우)에는 다리를 만들지 않고, 그렇지 않은 경우에는 다리를 만들어 준다
void mst() {
for (int i = 0; i < vec.size(); i++) {
int dist = vec[i].first.first;
int is1 = vec[i].first.second;
int is2 = vec[i].second;
if (dist < 2) continue;
if (union_island(is1, is2))
ret += dist;
}
}- 아래는
Kruskal Algorithm구현이고 두 섬을 연결할 때 부모섬을 같게 해주는 것과 동시에adj[][]에도 값을 추가해주어 두 섬이 연결되어 있다는쌍방향 노드를 만들어준다
Kruskal Algorithm 참고
int find(int u) {
if (u == parents[u]) return u;
else return find(parents[u]);
}
bool union_island(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
parents[u] = v;
adj[u].push_back(v);
adj[v].push_back(u);
return true;
}
else return false;
}🌉4. Connected or Disconnected
- 이렇게 만든
adj[][]를 통해 모든 섬이 연결되어 있는지 확인 - 먼저 1번 섬을
queue에 넣어주어 1번 섬은 방문했다는 표시를 해준다 - 이제 1번 섬에서 인접하고 아직 한 번도 방문되지 않은 섬을
queue에 넣어준다 - 이때 카운트를 해주어 총 섬의 수와 이 수가 같은지 확인한다
- 같다면 모든 섬이 연결되어 있다는 것
bool is_connected() {
int cnt = 1;
queue<int> q;
bool is_visited[i_MAX] = { false, };
q.push(1);
while (!q.empty()) {
int now = q.front();
q.pop();
is_visited[now] = true;
for (int i = 0; i < adj[now].size(); i++) {
int next = adj[now][i];
if (is_visited[next] == false) {
q.push(next);
cnt++;
}
}
}
if (cnt != num) return false;
else return true;
}🌉Source code
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl "\n"
const int MAX = 11;
const int i_MAX = 7;
const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };
using namespace std;
int ret = 0;
int N, M;
int num = 1;
int map[MAX][MAX];
bool visited[MAX][MAX];
int parents[i_MAX];
vector<int> adj[i_MAX];
vector<pair<pair<int, int>, int> >vec;
void input() {
cin >> N >> M;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> map[i][j];
}
int find(int u) {
if (u == parents[u]) return u;
else return find(parents[u]);
}
bool union_island(int u, int v) {
u = find(u);
v = find(v);
if (u != v) {
parents[u] = v;
adj[u].push_back(v);
adj[v].push_back(u);
return true;
}
else return false;
}
void bfs(int i, int j, int num) {
queue<pair<int, int> >q;
q.push(make_pair(i, j));
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny <= 0 || nx <= 0 || ny > N || nx > M) continue;
if (!visited[ny][nx] && map[ny][nx] == 1) {
map[ny][nx] = num;
visited[ny][nx] = true;
q.push(make_pair(ny, nx));
}
}
}
}
void init_island() {
for (int i = 1; i <= i_MAX; i++)
parents[i] = i;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (!visited[i][j] && map[i][j] == 1) {
visited[i][j] = true;
map[i][j] = num;
bfs(i, j, num);
num++;
}
}
}
num--;
}
void check_dist(int now, int y, int x) {
for (int i = 0; i < 4; i++) {
int ny = y;
int nx = x;
int dist = 0;
while (true) {
ny += dy[i];
nx += dx[i];
if (ny <= 0 || nx <= 0 || ny > N || nx > M ||
map[ny][nx] == now) break;
if (map[ny][nx] != 0) {
vec.push_back(make_pair(make_pair(dist, now), map[ny][nx]));
break;
}
dist++;
}
}
}
void mst() {
for (int i = 0; i < vec.size(); i++) {
int dist = vec[i].first.first;
int is1 = vec[i].first.second;
int is2 = vec[i].second;
if (dist < 2) continue;
if (union_island(is1, is2))
ret += dist;
}
}
void make_mst() {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (map[i][j] != 0)
check_dist(map[i][j], i, j);
}
}
sort(vec.begin(), vec.end());
mst();
}
bool is_connected() {
int cnt = 1;
queue<int> q;
bool is_visited[i_MAX] = { false, };
q.push(1);
while (!q.empty()) {
int now = q.front();
q.pop();
is_visited[now] = true;
for (int i = 0; i < adj[now].size(); i++) {
int next = adj[now][i];
if (is_visited[next] == false) {
q.push(next);
cnt++;
}
}
}
if (cnt != num) return false;
else return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
init_island();
make_mst();
if (is_connected())
cout << ret << endl;
else cout << -1 << endl;
return 0;
}
Born to be happy, Not perfect 🤍