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 | #include <stdio.h> #include <queue> #include <utility> #include <string.h> using namespace std; int dx[4] = { 1,-1, 0,0 }; int dy[4] = { 0,0,1,-1 }; int arr[105][105] = { 0 }; int n; int bridge(int isNum) { int chk[105][105]; memcpy(chk, arr, sizeof(arr)); queue<pair<int, pair<int, int>>> q; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (arr[i][j] == isNum) { q.push(make_pair(0, make_pair(i, j))); chk[i][j] = -1; } int rst = 0; while (!q.empty()) { int len = q.front().first; int y = q.front().second.first; int x = q.front().second.second; q.pop(); if ((arr[y][x] != isNum) && (arr[y][x] > 1)) { rst = len - 1; break; } for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx <= 0 || xx > n || yy <= 0 || yy > n) continue; if (chk[yy][xx] == -1) continue; chk[yy][xx] = -1; q.push(make_pair(len + 1, make_pair(yy, xx))); } } return rst; } void color(int y, int x, int c) { arr[y][x] = c; for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (arr[yy][xx] == 1) color(yy, xx, c); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &arr[i][j]); int c = 2; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (arr[i][j] == 1) { color(i, j, c); c++; } } int mini = 10000000000000; for (int i = 2; i < c; i++) { int tmp = bridge(i); if (mini > tmp) mini = tmp; } printf("%d", mini); } | cs |
정말 중요한 문제였다.
약간..등고선? 같은걸 그리는 문제라고 해야되나
이걸 해결하기 위해 DFS밖에 방법이 없다고 생각했는데,
오히려 BFS로 풀어버리니 훨씬 간단했다.
아주 중요했던 문제니, 잘 기억하자