백준 : 다리 만들기 2 c++

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

풀이

1. 섬들을 2번부터 시작해서 라벨링 한다!!

 -> bfs 이용

2. 이제 각 섬에서 다른 섬까지 연결 가능한 모든 다리 생성 후 vector에 저장

 -> 길이가 2 이상이여야됨!!

 -> 두개의 섬 라벨과 다리 길이 value로 이루어진 struct로 관리

 

3. 길이 작은 순으로 sort 후 크루스칼 

 

4. 모든 섬이 연결이 안됬으면 -1 출력

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

// 유니온파인드를 쓸거임
// 그 이전에 각 섬을 노드
// 연결가능한 모든 경우를 다 간선으로 만듬
int n, m;
int map[101][101];
int parent[10];


int d_r[4] = { 1,-1,0,0 };
int d_c[4] = { 0,0,1,-1 };

struct bridge {
	int a, b;
	int value;
};

bool cmp(bridge a, bridge b)
{
	return a.value < b.value;
}

int getParent(int x)
{
	if (parent[x] == x)
		return x;

	return parent[x] = getParent(parent[x]);
}

void connect(int x, int y)
{
	x = getParent(x);
	y = getParent(y);
	if (x > y)
		parent[x] = y;
	else
		parent[y] = x;
}

void bfs(int r, int c, int cnt)
{
	map[r][c] = cnt;
	queue<pair<int, int> > q;
	q.push(make_pair(r, c));

	while (!q.empty())
	{
		int now_r = q.front().first;
		int now_c = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int new_r = now_r + d_r[i];
			int new_c = now_c + d_c[i];
			if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= m)
				continue;
			if (map[new_r][new_c] == 1)
			{
				map[new_r][new_c] = cnt;
				q.push(make_pair(new_r, new_c));
			}
		}

	}

}

pair<int,int> try_bridge(int r, int c, int way)//첫번째는 길이, 두번째는 누구랑!
{
	int cnt = 0;
	while (true)
	{
		r += d_r[way];
		c += d_c[way];
		if (r < 0 || c < 0 || r >= n || c >= m)
			return make_pair(-1,-1);
		if (map[r][c] != 0)
			return make_pair(cnt, map[r][c]);

		cnt++;
	}

}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> map[i][j];

	int cnt = 2;

	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] == 1)
			{
				bfs(i, j, cnt);
				cnt++;
			}
		}
	//섬은 2번부터 cnt-1까지 있음!!
	//이제 가능한 모든 다리들 만들기!
	vector<bridge> v;
	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++)
		{
			if (map[i][j] != 0)
			{
				for (int k = 0; k < 4; k++)
				{
					int new_r = i + d_r[k];
					int new_c = j + d_c[k];
					if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= m)
						continue;
					if (map[new_r][new_c] == 0)//바다랑 겹쳐 있는 땅
					{
						if (try_bridge(i, j, k).first != -1)//-1이면 다리를 못짓는 다는 소리임
						{
							if (try_bridge(i, j, k).first >= 2)//다리 길이는 반드시 2 이상
							{
								bridge tmp;
								tmp.a = map[i][j];
								tmp.b = try_bridge(i, j, k).second;
								tmp.value = try_bridge(i, j, k).first;
								v.push_back(tmp);
							}
						}
					}
				}
			}
		}
	sort(v.begin(), v.end(), cmp);
	int answer = 0;

	for (int i = 2; i < cnt; i++)
		parent[i] = i;

	for (int i = 0; i < v.size(); i++)
	{
		if (getParent(v[i].a) != getParent(v[i].b))
		{
			connect(v[i].a, v[i].b);
			answer += v[i].value;
		}
	}

	int final_parent = getParent(2);
	for (int i = 3; i < cnt; i++)
	{
		if (getParent(i) != final_parent)
			answer = -1;
	}

	cout << answer << endl;
	return 0;
}