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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 | #include <stdio.h> #include <vector> #include <queue> #include <utility> #include <math.h> #include <string.h> using namespace std; vector<pair<int, int>> v(10005); int island = 2; int chk[10005] = { 0 }; int isChk[10005] = { 0 }; int bfs1(int a, int n, int m) { queue<pair<int, pair<int, int>>> q; //st,(cnt,island) memset(chk, 0, sizeof(chk)); memset(isChk, 0, sizeof(isChk)); int end = v[a].second, st = v[a].first; int cnt = 1; island = 2; isChk[st] = 1; isChk[end] = 1; chk[a] = 1; q.push(make_pair(end, make_pair(cnt, island))); int rst = 10000000; while (!q.empty()) { cnt = q.front().second.first; island = q.front().second.second; st = q.front().first; q.pop(); if (island == n) { rst = cnt; break; } for (int i = 1; i <= m; i++) { if (v[i].first == st && chk[i] == 0) { chk[i] = 1; int arrive = v[i].second; if (isChk[arrive] == 0) { q.push(make_pair(arrive, make_pair(cnt + 1, island + 1))); isChk[arrive] = 1; } }else if (v[i].second == st && chk[i] == 0) { chk[i] = 1; int arrive = v[i].first; if (isChk[arrive] == 0) { q.push(make_pair(arrive, make_pair(cnt + 1, island + 1))); isChk[arrive] = 1; } } } } return rst; } int bfs2(int a, int n, int m) { queue<pair<int, pair<int, int>>> q; //st,(cnt,island) memset(chk, 0, sizeof(chk)); memset(isChk, 0, sizeof(isChk)); int st = v[a].second, end = v[a].first; int cnt = 1; island = 2; isChk[st] = 1; isChk[end] = 1; chk[a] = 1; q.push(make_pair(end, make_pair(cnt, island))); int rst = 10000000; while (!q.empty()) { cnt = q.front().second.first; island = q.front().second.second; st = q.front().first; q.pop(); if (island == n) { rst = cnt; break; } for (int i = 1; i <= m; i++) { if (v[i].first == st && chk[i] == 0) { chk[i] = 1; int arrive = v[i].second; if (isChk[arrive] == 0) { q.push(make_pair(arrive, make_pair(cnt + 1, island + 1))); isChk[arrive] = 1; } } else if (v[i].second == st && chk[i] == 0) { chk[i] = 1; int arrive = v[i].first; if (isChk[arrive] == 0) { q.push(make_pair(arrive, make_pair(cnt + 1, island + 1))); isChk[arrive] = 1; } } } } return rst; } int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int st, end; scanf("%d %d", &st, &end); v[i].first = st; v[i].second = end; } int minN = 100000; for (int i = 1; i <= m; i++) { int tmp1 = bfs1(i, n, m); int tmp2 = bfs2(i, n, m); tmp1 = min(tmp1, tmp2); minN = min(minN, tmp1); } printf("%d\n", minN); } } | cs |
bfs 로 문제를 해결하긴 했으나, 시간초과가 걸린다
근데 실제 문제 풀이 방식은 엄청 간단하고 김빠지는 풀이였다.
아래 풀이를 보자
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <stdio.h> using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int st, end; scanf("%d %d", &st, &end); } printf("%d\n", n - 1); } } | cs |
어이가 없었다.
다행이다 그래도. 괜히 시간 낭비할뻔 했네