백준 17472번 - 다리 만들기 2 (C++)

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

 

삼성 A형 기출 문제로 좋은 문제다. 이전에 삼성 대학생 역량 어쩌구를 할 때도 이런 종류의 문제가 많았다. bfs, dfs 후 경로를 사용해 다익스트라를 사용한다는 문제가 있었다. 하지만 이 문제는 mst를 하는 문제이다.

 

1. bfs or dfs를 통해 각 섬의 번호를 매긴다. (그래프 탐색)

2. 그리고 다시한 번 bfs를 통해 각 섬끼리의 최소 거리를 구해 그래프를 구성한다. (bfs, 구현 능력)

3. 구성한 그래프를 통해 MST를 진행한다. (MST 프림 or 크루스칼)

 

그래프의 크기가 크지 않아서 시간을 생각하는 것 보다 코드를 어떻게 해야 간단하고 완벽하게 구성할 수 있을까 고민하는 것이 관건이이며, BFS, MST 같은 기본 알고리즘 구현을 할 수 있어야하는 좋은 문제였다. 

 

나도 오랜만에 MST를 구현하려니 기억이 안나서 예전 코드를 들여다봤다 ㅠ

 

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

int maps[101][101];
int N, M;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int num = 1;
int answer = 0;
queue<pair<int, int>> q;
bool visited[101][101] = {false,};
bool Range(int x, int y){
	return x > -1 && x < N && y > -1 && y < M;
}

void bfs(int k){		
	while(!q.empty()){
		int r = q.front().first;
		int c = q.front().second;
		q.pop();

		maps[r][c] = k;

		for(int i = 0; i < 4; i++){
			int nextx = r + dx[i];
			int nexty = c + dy[i];

			if(Range(nextx, nexty) && !visited[nextx][nexty] && maps[nextx][nexty] == 1){
				visited[nextx][nexty] = true;
				maps[nextx][nexty] = k;
				q.push({nextx, nexty});
			}
		}
	}
}

int board[11][11];
void setting(int r, int c){
	memset(visited, false, sizeof visited);

	queue<pair<int, int>> q;
	q.push({r, c});
	visited[r][c] = true;
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		//cout << maps[x][y] << " ";

		for(int i = 0; i < 4; i++){
			int nextx = x;
			int nexty = y;
			int dist = 0;
			while(true){
				dist++;
				nextx += dx[i];
				nexty += dy[i];

				if(!Range(nextx, nexty) || maps[nextx][nexty] == maps[x][y]) 
					break;
				else if(maps[nextx][nexty] > 0 && maps[nextx][nexty] != maps[x][y]){
					if(dist - 1 < 2) break;

					int a = maps[x][y];
					int b = maps[nextx][nexty];

					board[a][b] = min(board[a][b], dist - 1);
					board[b][a] = board[a][b];
					break;
				}
			}
		}

		for(int i = 0; i < 4; i++){
			int nextx = x + dx[i];
			int nexty = y + dy[i];

			if(Range(nextx, nexty) && !visited[nextx][nexty] && maps[x][y] == maps[nextx][nexty]){
				visited[nextx][nexty] = true;
				q.push({nextx, nexty});
			}
		}
	}
}

vector<pair<int, int>> vertex[11];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;


void setgraph() {
	for (int i = 1; i <= num - 1 ; i++) {
		for(int j = 1; j <= num - 1; j++){
			vertex[i].push_back({j, board[i][j]});
			vertex[j].push_back({i, board[i][j]});

		}
	}

	PQ.push({0, 1});
}

void PRIM() {
	bool mstVis[11] = {false};

	while (!PQ.empty()) {
		int here = PQ.top().second;
		int heredis = PQ.top().first;
		PQ.pop();

		if (mstVis[here] == true) continue;
		else mstVis[here] = true;
		
		answer += heredis;
		for (int i = 0; i < vertex[here].size(); i++) {
			int next = vertex[here][i].first;
			int nextdis = vertex[here][i].second;

			PQ.push(make_pair(nextdis, next));
		}
	}
}


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

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

	int sx, sy;

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(visited[i][j] == false && maps[i][j] == 1){
				q.push({i, j});
				bfs(num);
				num++;
				sx = i;
				sy = j;
			}
		}
	}

	for(int i = 0; i <= num; i++){
		for(int j = 0; j <= num; j++){
			board[i][j] = 100000;
		}	
	}
	bool check[10] = {false};

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(maps[i][j] > 0 && check[maps[i][j]] == false){
				check[maps[i][j]] = true;
				setting(i, j);
			}
		}
	}

	// for(int i = 0; i < N; i++){
	// 	for(int j = 0; j < M; j++){
	// 		cout << maps[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	// for(int i = 1; i <= num - 1; i++){
	// 	for(int j = 1; j <= num - 1; j++){
	// 		if(board[i][j] == 100000) cout << "IN ";
	// 		else cout << board[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	setgraph();
	PRIM();
	if(answer >= 100000) cout << -1 << '\n';
	else cout << answer << '\n';
}