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

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

17472번: 다리 만들기 2

 

이 문제에서는 섬과 바다를 2차원 배열의 형태로 제공합니다. 그리고 해당 섬들을 모두 잇는 최단 길이를 구하는 문제입니다. 

 

🎲 문제 풀이법

    1. 우선, 각각의 섬을 구별하는 작업부터 해주어야합니다. BFS를 이용해 각각의 섬에 인덱스를 부여해 구별하여 줍니다.

    2. 그다음 이중포문으로 배열 전체를 돌면서 섬이 있는 칸으로 부터 상하좌우로 검사를 해줍니다. 검사는 재귀함수를 통해 데이터 밖으로 나가거나, 출발섬과 같은 섬을 만날경우 실패하여 멈추고, 자신과 다른 섬을 만날경우 성공하여 해당 거리를 저장합니다. 이때, 무조건 저장하는것은 아니고 기존 경로와 비교하여 2칸이상 소요하면서 최단 거리일 경우에만 저장합니다.

    3. 위의 조건으로 최단 거리 경로를 구할경우 아래와 같은 값이 나오게 됩니다.

4. 이제 위에서 구한 경로별 거리값을 가지고 프림 알고리즘을 통해서 섬을 모두 잇는 최단 거리를 구해주면 됩니다. 

5. 프림 알고리즘은 [연결된 점]들과 붙어 있는 간선들 중에서 제일 값이 저렴한 간선을 연결 해주는 과정을 반복하는 알고리즘입니다. 모든 점들이 연결될 때 까지 반복하여 주면 됩니다.

6. 프림 알고리즘으로 간선을 연결 한 뒤 연결된 간선 가중치의 합을 구해 출력해주시면 정답이 나옵니다.

 

#include <stdio.h>
#include <string>
#include <fstream>
#include <iostream>
#include <list>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;



int N, M;

int table[110][110];
bool visited[110][110];
bool connected[110];

int path[110][110];
int cost[110];
int islandsSize;

struct Island
{
	int minX, minY, maxX, maxY;
	vector<pair<int, int>> list;
};
struct Path
{
	int from, to, cost;
};

void CalXp(int from, int x, int y, int len)
{
	if (x < 1 || x > N || y < 1 || y > M) return;

	if (table[x][y] == 0)
		CalXp(from, x + 1, y, len + 1);
	else {
		if ((path[from][table[x][y]] == 0 || path[from][table[x][y]] > len) && len > 1) {
			path[from][table[x][y]] = len;
			path[table[x][y]][from] = len;
		}
	}
}

void CalXm(int from, int x, int y, int len)
{
	if (x < 1 || x > N || y < 1 || y > M) return;

	if (table[x][y] == 0)
		CalXm(from, x - 1, y, len + 1);
	else {
		if ((path[from][table[x][y]] == 0 || path[from][table[x][y]] > len) && len > 1) {
			path[from][table[x][y]] = len;
			path[table[x][y]][from] = len;
		}
	}
}

void CalYp(int from, int x, int y, int len)
{
	if (x < 1 || x > N || y < 1 || y > M) return;

	if (table[x][y] == 0)
		CalYp(from, x, y + 1, len + 1);
	else {
		if ((path[from][table[x][y]] == 0 || path[from][table[x][y]] > len) && len > 1) {
			path[from][table[x][y]] = len;
			path[table[x][y]][from] = len;
		}
	}
}

void CalYm(int from, int x, int y, int len)
{
	if (x < 1 || x > N || y < 1 || y > M) return;

	if (table[x][y] == 0)
		CalYm(from, x, y - 1, len + 1);
	else {
		if ((path[from][table[x][y]] == 0 || path[from][table[x][y]] > len) && len > 1) {
			path[from][table[x][y]] = len;
			path[table[x][y]][from] = len;
		}
	}
}

void Rec(int x, int y, int idx)
{
	if (visited[x][y] || x < 1 || x > N || y < 1 || y > M) return;

	visited[x][y] = true;
	table[x][y] = idx;

	if (table[x + 1][y] == 1) Rec(x + 1, y, idx);
	if (table[x - 1][y] == 1) Rec(x - 1, y, idx);
	if (table[x][y + 1] == 1) Rec(x, y + 1, idx);
	if (table[x][y - 1] == 1) Rec(x, y - 1, idx);
}

void FindConnecting(int _island)
{
	for (int i = 0; i < islandsSize; i++)
	{
		if (path[_island][i] <= 0) continue;
		if (cost[i] == 0 || cost[_island] + path[_island][i] < cost[i])
		{
			cost[i] = cost[_island] + path[_island][i];
			FindConnecting(i);
		}
	}
}


int main()
{
	vector<Island> islands;
	vector<Path> paths;
	int count = 0, count2 = 0;


	cin >> N;
	cin >> M;
	queue<pair<int, int>> que;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++) {
			cin >> table[i][j];
		}
	}

	count = 1;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++) {
			if (visited[i][j] || table[i][j] == 0) continue;
			
			Island tmp;
			Rec(i, j, count);
			islands.push_back(tmp);
			count++;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++) {
			if (table[i][j] == 0) continue;

			CalXp(table[i][j], i + 1, j, 0);
			CalXm(table[i][j], i - 1, j, 0);
			CalYp(table[i][j], i, j + 1, 0);
			CalYm(table[i][j], i, j - 1, 0);
		}
	}


	int totalCost = 0, minCost = 2100000000;
	bool possible = false;
	pair<int, int> minWay;
	vector<int> connectedList;
	connected[1] = true;
	connectedList.push_back(1);

	while (true) {
		minCost = 2100000000;
		for (int i = 0; i < connectedList.size(); i++)
		{
			for (int j = 1; j < count; j++) {
				if (!connected[j] && path[connectedList[i]][j] > 1 && path[connectedList[i]][j] < minCost)
				{
					minWay.first = connectedList[i];
					minWay.second = j;
					minCost = path[connectedList[i]][j];
				}
			}
		}
		if (minCost == 2100000000) break;
		possible = true;
		connected[minWay.first] = true;
		connected[minWay.second] = true;
		connectedList.push_back(minWay.second);
		totalCost += minCost;
	}


    
	if (possible && connectedList.size() == count-1)
		printf("%d", totalCost);
	else
		printf("-1");


	return 0;
}

 

 

🍳 어려웠던점

    1. 섬 모양이 직사각형뿐일 거라고 지레 짐작한 점 (예재에 떡하니 ㄴ자 모양의 섬이 있었습니다.)

    2. 섬과 섬 사이를 다른 섬이 막고 있는 것을 고려 하지 않은점