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

문제 링크

---

www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

접근 방법

---

 알고리즘적으로 어렵다기 보다 구현할 부분들이 많아 시간이 오래 걸렸던 문제이다. 

 

 일단 모든 섬이 연결되어야 어떠한 답을 도출할 수 있다. 모든 섬을 최소 비용으로 연결한다는 부분에서 MST(최소신장트리)를 떠올릴 수 있다. 트리의 특성 중 하나는 간선의 수는 노드 수보다 하나 적다는 것이다. 이러한 조건을 사용하여 모든 섬이 연결되어 있는지를 알 수 있다. 

 

 그러면 섬과 섬 사이의 거리를 알아야 한다. 이런 사전작업은 BruteForce의 방법으로 해결을 하였다. 즉 단순무식하게 경우의 수를 모두 검사하였다.  

 

 그렇다면 섬과 섬사이의 거리를 구하기 위해서는 (1)섬의 정보들을 저장하고 (2)world[N][M]를 먼저 갱신하는 작업을 해야한다. 

 

(1)과 (2)의 작업을 거치게 된다면 이렇게 될것이다.

※하단 소스코드 BFS(int x, int y, int num)와 islandInfo() 함수 참고

 

 

여기서 갱신된 지도를 world[N][M]이라 하고, 섬의 정보들을 갖춘 2차원 벡터를 islands라 하였을 때, 이 두 가지의 정보로 섬과 섬사이의 거리를 구할 수 있다. 

 

 islands의 한 섬을 island라 하였을 때 island를 이루고 있는 모든 좌표에 대해 상하좌우 4방향으로 검사를 해야한다. 

어떠한 섬에 도달할 수 있다면 다리의 길이 값을 계속해서 최소로 갱신하여 준다.

 

 갱신이 완료되면 크루스칼 알고리즘을 적용하기 위해 비용을 기준으로 오름차순 정렬한다.

 

※하단 소스코드 islandConnect(vector<vector<pair<int, int>>> islands)와 go(pair<int, int> coord, int dir) 참고 

 

 

이제 정렬된 정보를 바탕으로 크루스칼 알고리즘을 적용하여 간선의 수를 count하는 동시에 다리 길이의 합도 구해준다. 최종적으로 count수가 섬의 수보다 1적다면 정답을 아니라면 -1을 return한다.

 

소스 코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int world[100][100];
pair<int, int> direction[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
bool visited[100][100];
int N, M;

typedef struct info {
	int x;
	int y;
	int cost;
};

void printAll(vector<info> connectInfo, vector<vector<pair<int, int>>> islands) {
//문제 풀다가 출력할 일 있으면 사용하세요! 
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << world[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	for (int i = 1; i < islands.size(); i++) {
		cout << "islands num: " << i << "\n";
		for (int j = 0; j < islands[i].size(); j++) {
			cout << "[" << islands[i][j].first << ", " << islands[i][j].second << "] ";
		}
		cout << "\n";
	}

	cout << "\n";
	for (int i = 0; i < connectInfo.size(); i++)
		cout << "island1: " << connectInfo[i].x << " island2: " << connectInfo[i].y << " length: " << connectInfo[i].cost << endl;
}

bool inRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < M);
}

bool comp(info &a, info &b) {
	return a.cost < b.cost;
}

vector<pair<int, int>> BFS(int x, int y, int num) {

	vector<pair<int, int>> retV;
	queue<pair<int, int>> q;

	retV.push_back({ x,y });
	q.push({ x,y });
	visited[x][y] = true;
	world[x][y] = num;

	while (!q.empty()) {
		
		int now_x = q.front().first;
		int now_y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int next_x = now_x + direction[i].first;
			int next_y = now_y + direction[i].second;

			if (inRange(next_x, next_y) && !visited[next_x][next_y] && world[next_x][next_y] != 0) {
				q.push({ next_x, next_y });
				retV.push_back({ next_x, next_y });
				visited[next_x][next_y] = true;
				world[next_x][next_y] = num;
			}
		}
	}

	return retV;
}

vector<vector<pair<int, int>>> islandInfo() {

	vector<vector<pair<int, int>>> islands;
	int islandNum = 1;
	islands.push_back({ {-1,-1} }); //섬의 번호는 1부터 -> index와 섬의 번호를 일치 시킴

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++) 
			if (world[i][j] != 0 && !visited[i][j]) {
				vector<pair<int, int>> island = BFS(i, j, islandNum);
				islands.push_back(island);
				islandNum++;
			}

	return islands;
}


info go(pair<int, int> coord, int dir) {

	int x = coord.first;
	int y = coord.second;
	int from = world[x][y];
	int to = from;
	int len = 0;

	while (true) {

		x += direction[dir].first;
		y += direction[dir].second;
		
		if (inRange(x, y)) {
			if (world[x][y] == 0)
				len++;
			else if (world[x][y] == from)
				break;
			else {
				to = world[x][y];
				break;
			}
		}
		else
			break;
	}
	return { from, to, len };
}


vector <info> islandConnect(vector<vector<pair<int, int>>> islands) {

	map <pair<int, int>, int> costInfo;
	vector <info> retV;

	for (int num = 1; num < islands.size(); num++) {
		vector<pair<int, int>> island = islands[num];
		for (int i = 0; i < island.size(); i++) {
			pair<int, int> coord = island[i];
			for (int dir = 0; dir < 4; dir++) {

				info state = go(coord, dir);
				
				if (state.cost < 2 || state.y == state.x) 
					continue;
				else {
					if (state.x < state.y) { //간선은 양방향 이므로 중복되는 정보를 저장하지 않음
						if (costInfo.count({ state.x, state.y }) == 0)
							costInfo[{ state.x, state.y }] = state.cost;
						else
							costInfo[{ state.x, state.y }] = min(costInfo[{ state.x, state.y }], state.cost);
					}
				}
			}
		}
	}

	for (pair<pair<int, int>, int> cost : costInfo)
		retV.push_back({cost.first.first, cost.first.second, cost.second });
	sort(retV.begin(), retV.end(), comp);

	return retV;
}

int find(int a, vector<int> &parent) {
	
	if (parent[a] == a)
		return a;
	if (parent[a] == -1)
		parent[a] = a;

	return parent[a] = find(parent[a], parent);
}

bool Union(int a, int b, vector<int> &parent) {

	a = find(a, parent);
	b = find(b, parent);

	if (a != b) {
		parent[b] = a;
		return true;
	}
	return false;
}

int solve() {

	int result = 0;
	int cnt = 0;

	vector<vector<pair<int, int>>> islands = islandInfo();
	vector <info> connectInfo = islandConnect(islands);
	vector <int> parent(islands.size(), -1); 
    
    //정렬된 정보를 바탕으로 크루스칼 알고리즘 실행
	for (int i = 0; i < connectInfo.size(); i++) { 
		if (Union(connectInfo[i].x, connectInfo[i].y, parent)) {
			cnt++;
			result += connectInfo[i].cost;
		}
	}
	
	//printAll(connectInfo, islands);
    //islands의 index와 섬의 번호를 강제로 일치시켜놓았기 때문에 size는 섬의 수보다 1더 크다.
	return result = (cnt == islands.size() - 2) ? result : -1; 
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;
	
	for (int i = 0; i < N; i++) 
		for (int j = 0; j < M; j++) 
			cin >> world[i][j];
		
	cout << solve();

}

개발 환경 : VS2017

질문, 지적 환영합니다!