반응형
문제 링크:https://www.acmicpc.net/problem/2146
<문제 풀이> BFS
섬의 육지에서 시작해서 BFS로 다른 섬의 육지에 최초로 만나는 지점이 다리를 놓을 수 있는 방법 중에 하나입니다.
그래서 문제를 해결하기 위해서
1. bfs로 섬을 구분한다.
10
1 1 1 0 0 0 0 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0
2. i번째 섬의 모든 육지를 큐에 담고 최초로 다른 섬과 만날 때까지 최단거리를 갱신한다.
-> 모든 섬에 대해서 bfs를 돌리고 최솟값을 구하면 됩니다.
<C++ 소스 코드>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
#define X first
#define Y second
int board[100][100];
int visited1[100][100]; // 섬 구분
int visited2[100][100]; // 최단 거리
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1 , 0, -1, 0 };
int n;
int flag = 1;
int res = INT_MAX;
void bfs1() {// 섬 구분
queue<pair<int, int> > Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 1 && !visited1[i][j]) {
Q.push({ i, j });
visited1[i][j] = true;
board[i][j] = flag;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (board[nx][ny] != 1 || visited1[nx][ny])continue;
Q.push({ nx, ny });
board[nx][ny] = flag;
visited1[nx][ny] = true;
}
}
flag++;
}
}
}
flag--;
}
void bfs2() { //최단거리
flag = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == flag) {
queue<pair<int, int> > Q;
Q.push({ i, j });
visited2[i][j] = 1;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
if (visited2[nx][ny] && visited2[nx][ny] <= visited2[cur.X][cur.Y] + 1)continue;
if (board[nx][ny] == flag) {
visited2[nx][ny] = 1;
Q.push({ nx, ny });
}
else if (board[nx][ny] == 0) {
visited2[nx][ny] = visited2[cur.X][cur.Y] + 1;
Q.push({ nx, ny });
}
else if (board[nx][ny] != flag) {
res = min(res, visited2[cur.X][cur.Y] - 1);
}
}
}
flag++;
fill(&visited2[0][0], &visited2[99][100], 0);
}
}
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
}
}
bfs1();
bfs2();
cout << res;
return 0;
}
|
cs |
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 6593번] 상범 빌딩 (0) | 2021.11.19 |
---|---|
[백준 5014번] 스타트링크 (0) | 2021.11.19 |
[백준 5427번] 불 (0) | 2021.11.17 |
[백준 7562번] 나이트의 이동 (0) | 2021.11.16 |
[백준 10026번] 적록색약 (0) | 2021.11.05 |