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 |