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

 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

2일 정도 걸렷는데 

이거 무슨 문제가 왜이리 더러운지 ㅋㅋ 아 뭔가 다시 정리해서 풀어봐야할듯하네요 

골드 어려워 ~

#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
using namespace std;

void Prints(vector<vector<char>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}
struct Point {
	int r;
	int c;
	int cnt = 0;
	int round = 0;
	bool bCheck = false;
};
int main() {
	int n;
	cin >> n;
	
	queue<Point>q;
	queue<Point>round;
	vector<int>tmpVisited(n, 0);
	vector<vector<int>>bVisited(n, tmpVisited);
	vector<vector<int>>bVisitedt(n, tmpVisited);
	vector<vector<int>>maps;
	int dirR[] = { 1,-1,0,0 };
	int dirC[] = { 0,0,1,-1 };
    //섬 지역 나누기 
	for (int i = 0; i < n; i++) {
		vector<int>tmpMaps;
		for (int j = 0; j < n; j++) {
			int tmp;
			cin>> tmp;
			tmpMaps.push_back(tmp);
		}
		maps.push_back(tmpMaps);
	}

	int roundCount = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			bool bCheck = false;
			if (maps[i][j] == 1 && bVisited[i][j] == 0) {
				bCheck = true;
				Point tmpPoint;
				tmpPoint.r = i;
				tmpPoint.c = j;
				tmpPoint.round = roundCount;
				round.push(tmpPoint);
				q.push(tmpPoint);
				bVisited[i][j] = roundCount;
				
				while (!round.empty()) {
					Point start = round.front();
					round.pop();
					bool bFind = false;
					for (int z = 0; z < 4; z++) {
						int tmpDirR = start.r + dirR[z];
						int tmpDirC = start.c + dirC[z];
						if (tmpDirR == -1 || tmpDirC == -1 || tmpDirR >= n || tmpDirC >= n) {
							continue;
						}
						
						if (maps[tmpDirR][tmpDirC] == 1 && bVisited[tmpDirR][tmpDirC] == 0) {
							bVisited[tmpDirR][tmpDirC] = roundCount;
							maps[tmpDirR][tmpDirC] = 1;
							Point p;
							p.c = tmpDirC;
							p.r = tmpDirR;
							bFind = true;
							p.round = roundCount;
							round.push(p);
							q.push(p);
							//bCheck = false;

						}
						
						
					}
					

				}
				roundCount++;
				
			}
			


		}
	}

	Point git;
	git.c = 0;
	git.r = 0;
	git.round = -1;
	git.bCheck = true;

	q.push(git);
	int max = 0;
	int ggCount = 1;
	vector<int>maxCount;
    //bfs 각 섬 다리 짓기
	bool bEnd = false;
	while (!q.empty()) {
		Point start = q.front();
		q.pop();
		if (bEnd == true) {
			break;
		}
		
		if (start.bCheck == true && q.size() > 1) {
			
			ggCount++;
			Point git;
			git.c = 0;
			git.r = 0;
			git.round = -1;
			git.bCheck = true;
			q.push(git);
			continue;
		}
		//n+1 지점 탐색
		for (int i = 0; i < 4; i++) {
			if (maps[start.r][start.c] == ggCount) {
				int tmpDirR = start.r + dirR[i];
				int tmpDirC = start.c + dirC[i];
				if (tmpDirR == -1 || tmpDirC == -1 || tmpDirR >= n || tmpDirC >= n) {
					continue;
				}

				if (maps[tmpDirR][tmpDirC] == 0 && bVisited[tmpDirR][tmpDirC] == 0&&start.bCheck==false&&start.round!=-1) {

					Point p;
					p.c = tmpDirC;
					p.r = tmpDirR;
					p.cnt = start.cnt + 1;
					
					p.round = start.round;
					q.push(p);
					maps[tmpDirR][tmpDirC] = ggCount + 1;
					bVisited[tmpDirR][tmpDirC] = start.round;
				   //n+2 지점 탐색
					for (int z = 0; z < 4; z++) {
						int tmpDirRs = tmpDirR + dirR[z];
						int tmpDirCs = tmpDirC + dirC[z];
						if (tmpDirRs == -1 || tmpDirCs == -1 || tmpDirRs >= n || tmpDirCs >= n) {
							continue;
						}
						//지역이 다른섬 만나곳 모으기 
						if (maps[tmpDirRs][tmpDirCs] != 0&&bVisited[tmpDirR][tmpDirC]!=bVisited[tmpDirRs][tmpDirCs]&& bVisited[tmpDirRs][tmpDirCs]!=0&& bVisited[tmpDirR][tmpDirC] !=0&&start.bCheck==false) {
							
							maxCount.push_back(start.cnt + 1 + (maps[tmpDirRs][tmpDirCs] - 1));
					
						}

					}
				

				}


			}

		}

	}
  
	sort(maxCount.begin(), maxCount.end());
	cout << maxCount[0];

	return 0;
}

'알고리즘 공부' 카테고리의 다른 글

백준 케빈 베이컨의 6단계 법칙  (0) 2023.07.12
백준 연결 요소의 개수  (0) 2023.07.12
백준 dfs와 bfs  (0) 2023.07.11
백준 안전 영역  (0) 2023.07.09
백준 알파벳  (0) 2023.07.09

+ Recent posts