백준 2146 c++ "다리 만들기" -[PlusUltraCode]

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

2146번: 다리 만들기

 

[필자 사고]

BFS탐색문제이다.

 

먼저 각 섬을 고유의 번호로 분리 시켜야 한다.

 

필자는 한번의 BFS 탐색을 이용해 분리시켰다.

 

다음으로 고유의 땅과 바다가 인접한 sero와garo 인덱스들을 찾아 최단거리 알고리즘을 이용하여 전체 탐색 해주었따.

 

시간복잡도를 계싼해보면 O(N^3logn) 으로 생각이 든다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int, int> Node;
typedef struct upNode {
	int count;
	int sero;
	int garo;
	
}upNode;
struct cmp {
	bool operator()(upNode a, upNode b) {
		return a.count > b.count;
	}
};

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

int N;

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

vector<vector<int>> Arr;
vector<vector<bool>> numberVisited;

void Input() {
	cin >> N;
	Arr.resize(N);
	numberVisited.resize(N);
	
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
		numberVisited[i].resize(N, false);
		
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr[i][k];
		}
	}
}
//1번섬은 다 사라지고 2번부터 시작
void MakeNumbering_BFS(int sero,int garo,int number) {
	numberVisited[sero][garo] = true;
	if (Arr[sero][garo] == 0)return;
	queue<Node> myQueue;
	myQueue.push({ sero,garo });
	int nowNumber = Arr[sero][garo];
	Arr[sero][garo] = number;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				numberVisited[nextSero][nextGaro] == false &&
				Arr[nextSero][nextGaro] == nowNumber) {
				numberVisited[nextSero][nextGaro] = true;
				Arr[nextSero][nextGaro] = number;
				myQueue.push({ nextSero,nextGaro });
			}
		}
	}
}vector<vector<bool>> visited;

int minimerDari(int sero, int garo) {
	visited.clear();
	visited.resize(N);
	for (int i = 0; i < N; i++) {
		visited[i].resize(N, false);
	}
	priority_queue<upNode, vector<upNode>, cmp> pq;
	pq.push({ 0,sero,garo });
	int nowNumber = Arr[sero][garo];
	int minPath = -1;
	while (!pq.empty()) {
		int nowSero = pq.top().sero;
		int nowGaro = pq.top().garo;
		int acCount = pq.top().count;
		pq.pop();
		if (Arr[nowSero][nowGaro] !=0&&Arr[nowSero][nowGaro]!=nowNumber) {
			minPath = acCount;
			return minPath;
		}
		if (visited[nowSero][nowGaro] == true)continue;
		visited[nowSero][nowGaro] = true;
	
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				Arr[nextSero][nextGaro] != nowNumber &&
				visited[nextSero][nextGaro] == false) {
				pq.push({ acCount + 1,nextSero,nextGaro });
			}
		}
	}
	return 99999;
}
//만약 -1을 리턴하면 배열내에 최단거리가 없는거임

void searchMinDari() {
	int Result = 9999999;
	int count = 99999999;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (Arr[i][k] != 0) {
				bool check = false;
				for (int j = 0; j < 4; j++) {
					int nextSero = i + dy[j];
					int nextGaro = k + dx[j];

					if (Inside(nextSero, nextGaro) &&
						Arr[nextSero][nextGaro] == 0) {
						check = true;
						break;
					}
				}
				if (check == true) {
					count= minimerDari(i,k);
					if (Result > count) {
						Result = count;
					}
				}

			}
		}
	}

	cout << Result-1;
}


void Print() {
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cout << Arr[i][k] << " ";
		}
		cout << '\n';
	}
}

void Solve() {
	int number = 2;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			if (numberVisited[i][k] == false) {
				MakeNumbering_BFS(i, k, number);
				if (Arr[i][k] == number) {
					number++;
				}
			}
		}
	}//섬을 구별하기
	searchMinDari();
	//각 섬 하나하나 마다 가장 가까운 섬 구하기
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Solve();
}