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

문제

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

BFS, DFS, MST 개념이 다 들어간 문제이고 단계적으로 풀이하여 문제에서 요구하는 바를 구현할 수 있는지가 중요한듯 합니다.

---

풀이순서

1. 입력으로 받은 데이터의 섬마다 번호를 매겨준다. (BFS 사용)

2. 상하좌우로 각 섬마다 연결될 수 있는 다리가 있는지 탐색하고 연결이 가능하면 경로에 추가한다. (DFS 사용)

3. 추가된 경로들을 가지고 최단거리를 구한다. (MST사용)

 

---

풀이

1. 먼저 BFS로 각 섬마다의 번호를 설정해줍니다. (1이 나오는 곳부터 시작하여 BFS탐색을 통해 연결된 모든 섬들을 같은 번호로 설정해주고 각 좌표값들을 island에 넣어줍니다.)

2. enum을 활용하여 한 방향으로만 진행이 가능한 DFS를 수행하여 다른 섬 까지 도달 할 수 있는지 확인해줍니다.(이때 위에서 각 섬의 번호에 해당하는 좌표를 넣어준 island배열이 활용됩니다)

3. MST를 수행하여 최단 거리를 구하고 정답을 출력!

 

---

코드

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <queue>
#include <limits.h>
#include <memory.h>
#include <sstream>
using namespace std;

#define endl "\n"
#define ll long long
#define INF 987654321

typedef pair<int, int> Pair;
typedef tuple<int, int, int> Tuple;

int n, m;

int fillBoardNum = 1;
bool visit[11][11];
int lastIdx = 0;
vector<vector<Pair>> islands;
bool visitI[11];

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

int ret = 0;
int adj[11][11];
int parent[11];
priority_queue<Tuple, vector<Tuple>, greater<Tuple>> pq;

enum
{
	LEFT = 1,
	BOTTOM = 2,
	RIGHT = 3,
	UP = 4,
};

int find(int a)
{
	if (a == parent[a]) return a;
	return parent[a] = find(parent[a]);
}

void merge(int a, int b)
{
	a = find(a); b = find(b);
	if (a != b) parent[b] = a;
}

// island에 fillBoardNum순서대로 같은 번호의 섬들의 좌표를 다 넣는다.
void BFS(int row, int col)
{
	visit[row][col] = true;
	queue<Pair> q;
	q.push({ row, col });
	adj[row][col] = fillBoardNum;
	islands[fillBoardNum].push_back({row, col});

	while (!q.empty())
	{
		auto now = q.front(); q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int nr = dy[i] + now.first;
			int nc = dx[i] + now.second;
			if (nr > 0 && nr <= n && nc > 0 && nc <= m)
			{
				if (!visit[nr][nc] && adj[nr][nc] != 0)
				{
					adj[nr][nc] = fillBoardNum;
					visit[nr][nc] = true;
					q.push({ nr, nc });
					islands[fillBoardNum].push_back({ nr, nc });
				}
			}
		}
	}
}

void DFS(int startRow, int startCol, int curRow, int curCol, int dir, int boardNum, int depth)
{
	int nr = curRow; int nc = curCol;
	if (dir == LEFT) --nc;
	else if (dir == BOTTOM) ++nr;
	else if (dir == RIGHT) ++nc;
	else if (dir == UP) --nr;

	if (nr > 0 && nr <= n && nc > 0 && nc <= m)
	{
		if (adj[nr][nc] == boardNum) return;
		if (adj[nr][nc] == 0)
		{
			DFS(startRow, startCol, nr, nc, dir, boardNum, depth + 1);
		}
		else if (adj[nr][nc] != boardNum)
		{
			if (depth >= 2 && visitI[adj[nr][nc]] == false)
			{
				pq.push({ depth, adj[startRow][startCol], adj[nr][nc] });
				visitI[adj[nr][nc]] = true;
			}
		}
	}
	else return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	islands.resize(11);
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			cin >> adj[i][j];
		}
	}

	// fill board
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (adj[i][j] != 0 && visit[i][j] != true)
			{
				BFS(i, j); ++fillBoardNum;
			}
		}
	}

	for (int i = 1; i <= 10; ++i)
	{
		if (islands[i].size() != 0)
		{
			lastIdx = i;
		}
	}

	// fill pathes
	for (int i = 1; i <= lastIdx; ++i)
	{
		for (auto pos : islands[i])
		{
			visitI[i] = true;
			for (int dir = 1; dir <= 4; ++dir)
			{
				DFS(pos.first, pos.second, pos.first, pos.second, dir, adj[pos.first][pos.second], 0);
			}
			memset(visitI, false, sizeof(visitI));
		}
	}

	// MST
	for (int i = 1; i <= lastIdx; ++i)
	{
		parent[i] = i;
	}

	int cnt = 0;
	while (!pq.empty())
	{
		auto now = pq.top(); pq.pop();
		int u = get<1>(now);
		int v = get<2>(now);
		int w = get<0>(now);

		if (find(u) != find(v))
		{
			++cnt;
			ret += w;
			merge(u, v);
		}
	}

	if (cnt == lastIdx - 1) cout << ret << endl;
	else cout << -1 << endl;

	return 0;
}