728x90
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
BFS로 섬을 체크하고 가장 짧은 다리를 놓기 위해 또 한 번 더 BFS를 해줘야 한다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<vector<int>> v(n, vector<int>(n));
vector<vector<bool>> visited(n, vector<bool>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> v[i][j];
}
}
int number = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && v[i][j] == 1) {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
v[cur.first][cur.second] = number;
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
for (int i = 0; i < 4; i++) {
int row = cur.first + dx[i];
int col = cur.second + dy[i];
if (row < n && row >= 0 && col < n && col >= 0 && v[row][col] == 1) {
q.push(make_pair(row, col));
}
}
}
}
number++;
}
}
}
int minDistance = 100000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (v[i][j] != 0) {
visited = vector<vector<bool>>(n, vector<bool>(n, false));
int start = v[i][j];
queue<tuple<int, int, int>> q;
q.push(make_tuple(i, j, 0));
while (!q.empty()) {
tuple<int, int, int> cur = q.front();
q.pop();
if (v[get<0>(cur)][get<1>(cur)] != 0 && v[get<0>(cur)][get<1>(cur)] != start) {
if (get<2>(cur) - 1 < minDistance)
minDistance = get<2>(cur) - 1;
break;
}
if (!visited[get<0>(cur)][get<1>(cur)]) {
visited[get<0>(cur)][get<1>(cur)] = true;
for (int i = 0; i < 4; i++) {
int row = get<0>(cur) + dx[i];
int col = get<1>(cur) + dy[i];
int distance = get<2>(cur);
if (row < n && row >= 0 && col < n && col >= 0 && v[row][col] != start) {
q.push(make_tuple(row, col, distance + 1));
}
}
}
}
}
}
}
cout << minDistance;
return 0;
}
728x90
'알고리즘 문제' 카테고리의 다른 글
| [백준] 15684번 사다리 조작 (0) | 2021.01.22 |
|---|---|
| [백준] 2573번 빙산 (0) | 2021.01.21 |
| [백준] 16236번 아기 상어 (0) | 2021.01.21 |
| [백준] 13460번 구슬 탈출 2 (0) | 2021.01.20 |
| [백준] 2458번 키 순서 (0) | 2021.01.19 |
