[C++] 백준 17472번: 다리 만들기 2

🔗 문제

17472번: 다리 만들기 2

17472번: 다리 만들기 2

제한

• 1 ≤ N, M ≤ 10
• 3 ≤ N×M ≤ 100
• 2 ≤ 섬의 개수 ≤ 6

 

✏️ 풀이

 

✍️ 문제 정리

다리를 설치해서 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.

 

[변수]

NxM 맵

• 바다 0
• 땅 1

 

[다리 설치 조건]

• 다리는 바다에만 건설할 수 있다.
• 다리의 방향은 한 방향이다
• 다리의 길이는 2 이상이다.
• 다리의 양끝은 인접한 바다 위에 있어야 한다. (섬과 닿는 부분은 길이로 치지 않는다)
• 섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.
• 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다.
  • 중첩하는 다리의 길이를 따로 구해주지 않아도 된다 🥰

 

---

[해야할 일]

1. 섬을 구한다. (BFS)
2. 섬의 모든 위치에서 4방 직선으로 나아가며 다리를 설치해본다.
3. 모든 섬이 연결될 수 있을 때 다리의 최소 길이를 출력한다.
4. 불가능하면 -1

---

사고의 흐름.. (안 읽어도 됨 그냥 일기임)

냅다 직선으로 다리를 설치하는걸 어찌 저찌해도 이 다리가 두 섬을 잇는 최소의 길이를 어떻게 보장할 수 있을지 생각을 해야한다. 또한 다리로 모든 섬이 연결되었는지는 어떻게 관리할지 생각을 해보자.

 

아이디어 1

입력이 작으니 모든 방향으로 탐색하되 그 값을 dp[][]로 만들어서 최소 값을 갱신하자.

그 후, 임의의 섬을 시작으로 dp로 연결된 섬 중에 방문하지 않되 최소값을 골라 넣자!

나는 이 아이디어도 좋다고 생각한다. 

 

아이디어 2

다리가 겹칠 때 면적 빼줘야 하는 줄 알고 유야무야 어찌저찌 다른 방법을 생각하다가 아이디어2로 넘어가게 되었다.

잘 생각해보니 이게 최소 스패닝 트리 문제고 pq로 넘어가면 … 크루스칼이잖아? 이렇게 되면 모든 섬이 연결되었는지도 대번에 알 수 있어서 대놓고 유니온 파인드 문제였구나라는 생각까지 들었다. (아니면 죄송)

그리고 이걸 다리 겹침엔 어떻게 적용하지 고민하며 문제를 다시 읽다가 겹치는 다리의 길이를 따로 쳐준다는 걸 알게 되서 바로 적용으로 넘어갔다.

 

각 섬을 그래프의 노드라고 생각하고 {from, to , weight} 를 최소 간선 기준으로 뽑으며 union-find를 해주면 문제가 깔끔하게 풀린다.

---

[실수한 부분 ]

 

예제랑 반례는 다 맞는데 틀렸습니다를 많이 봤다.

원인은 조건이 다리를 설치했다면, 그 방향으로 더 이상 진행하지 않아도 되는데  조건 처리를 잘 못 해주어 len의 길이가 필요 이상으로 많이 생기는 문제가 있었다. 

 

조건을 이것 저것 맞춰주다보면 코드가 엉망이 될 때가 있는데 이러면 조건을 인지하고 있어도 실수를 많이 한다.. 

코드를 더 가독성 좋게 짜고 싶다 !

 

int make_bridge(const int _x, const int _y, const int from)
{
	int to = 0;
	for (int d = 0; d < 4; ++d)
	{
		x = _x; y = _y;

		for (int len = 0; ; ++len)
		{
			x += dx[d]; y += dy[d];
			to = map[x][y];

			if (!isValid(x, y) || from == to) break;

			if (to != 0 && from != to)
			{
				**if (len > 1)**
					weight.push_back({ len, {to, from} });
				break;
			}

		}
	}

	return -1;
}

 

💾  소스

#include <iostream>
#include <queue>
#include <algorithm>
#include <memory.h>
#include <vector>

typedef std::pair<int, int> pii;
typedef std::pair<int, pii> T;

const int N_MAX = 10 + 1;
const int ISLAND_MAX = 7;

const int dx[4] = { 0, -1, 1, 0 };
const int dy[4] = { 1, 0, 0, -1 };

int N, M;
bool visited[N_MAX][N_MAX] = { false, };
int map[N_MAX][N_MAX] = { 0, };
int root[ISLAND_MAX];
std::vector<T> weight;

pii tmp;
int x, y;

bool isValid(const int x, const int y)
{
	if (x < 0 || y < 0 || x >= N || y >= M)
		return false;
	return true;
}

void show()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			std::cout << map[i][j] << " ";
		}
		std::cout << "\\n";
	}
}

int find(const int x)
{
	if (root[x] < 0) return x;
	return root[x] = find(root[x]);
}

bool merge(const int x, const int y)
{
	int r1 = find(x);
	int r2 = find(y);

	if (r1 == r2) return false;

	if (root[r1] > root[r2])
	{
		root[r1] += root[r2];
		root[r2] = r1;
	}
	else
	{
		root[r2] += root[r1];
		root[r1] = r2;
	}
	return true;
}

void find_islands(const int _x, const int _y, const int idx, std::vector<pii>& output)
{
	std::queue<pii> q;
	q.emplace(_x, _y);

	output.push_back({ _x, _y });
	map[_x][_y] = idx;

	while (!q.empty())
	{
		tmp = q.front();
		q.pop();

		for (int d = 0; d < 4; ++d)
		{
			x = tmp.first + dx[d];
			y = tmp.second + dy[d];

			if (!isValid(x, y) || visited[x][y] || map[x][y] != 1)
				continue;

			visited[x][y] = true;
			q.emplace(x, y);
			output.push_back({ x, y });
			map[x][y] = idx;
		}
	}

}

int make_bridge(const int _x, const int _y, const int from)
{
	int to = 0;
	for (int d = 0; d < 4; ++d)
	{
		x = _x; y = _y;

		for (int len = 0; ; ++len)
		{
			x += dx[d]; y += dy[d];
			to = map[x][y];

			if (!isValid(x, y) || from == to) break;

			if (to != 0 && from != to)
			{
				if (len > 1)
					weight.push_back({ len, {to, from} });
				break;
			}

		}
	}

	return -1;
}

int getAnswer()
{
	int answer = 0;
	int idx = 0;

	// 1. 섬의 위치와 개수를 파악한다.
	std::vector<std::vector<pii>> islands;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (map[i][j] == 1 && !visited[i][j])
			{
				std::vector<pii> input;
				find_islands(i, j, ++idx, input);
				islands.push_back(input);
			}
		}
	}

	//2. 섬에서부터 다리를 찾아보자 -> bridge 연결할 때 최소 연결 다리 생성
	std::fill(root, root + islands.size()+1, -1);
	idx = 0;
	for (const auto& pos : islands) // 한 섬을 꺼내서
	{
		++idx;
		for (const auto&[x, y] : pos) // 그 섬의 모든 위치에서 다리를 만들어보자
		{
			make_bridge(x, y, idx);
		}
	}

	std::sort(weight.begin(), weight.end());
	for (int i = 0; i < weight.size(); ++i)
	{
		if (merge(weight[i].second.first, weight[i].second.second))
		{
			answer += weight[i].first;
		}
	}

	for (int i = 1; i <= islands.size(); ++i)
	{
		if (root[i] * -1 == islands.size())
			return answer;
	}

	return -1;
}

int main()
{
	std::cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			std::cin >> map[i][j];
		}
	}

	std::cout << getAnswer();

	return 0;
}