<Baekjoon> #17472_MST, Kruskal, brute force, graph 다리 만들기2 c++

Google 아니고 Joogle·2022년 5월 12일
0

SAMSUNG SW Test

목록 보기
34/39
post-thumbnail

#17472 다리 만들기2

🌉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;

}

profile
Backend 개발자 지망생

0개의 댓글