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 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 | #include <stdio.h> #include <vector> #include <queue> #include <algorithm> using namespace std; vector<int> rstVec; typedef struct _cur { int a; int b; int c; }cur; int chk[201][201][201] = { 0 }; void bfs(int maxA, int maxB, int maxC) { queue<cur> q; q.push({ 0,0,maxC }); chk[0][0][maxC] = 1; while (!q.empty()) { int curA = q.front().a; int curB = q.front().b; int curC = q.front().c; q.pop(); if (curA == 0) { rstVec.push_back(curC); } //A->B if (curA + curB > maxB) { int sum = curA + curB; int tmpB = maxB; int tmpA = sum - tmpB; if (chk[tmpA][tmpB][curC] == 0) { chk[tmpA][tmpB][curC] = 1; q.push({ tmpA, tmpB, curC }); } } else { int sum = curA + curB; int tmpB = curA + curB; int tmpA = 0; if (chk[tmpA][tmpB][curC] == 0) { chk[tmpA][tmpB][curC] = 1; q.push({ tmpA, tmpB, curC }); } } //A->C if (curA + curC > maxC) { int sum = curA + curC; int tmpC = maxC; int tmpA = sum - tmpC; if (chk[tmpA][curB][tmpC] == 0) { chk[tmpA][curB][tmpC] = 1; q.push({ tmpA, curB, tmpC }); } } else { int sum = curA + curC; int tmpC = curA + curC; int tmpA = 0; if (chk[tmpA][curB][tmpC] == 0) { chk[tmpA][curB][tmpC] = 1; q.push({ tmpA, curB, tmpC }); } } //B->A if (curA + curB > maxA) { int sum = curA + curB; int tmpA = maxA; int tmpB = sum - tmpA; if (chk[tmpA][tmpB][curC] == 0) { chk[tmpA][tmpB][curC] = 1; q.push({ tmpA, tmpB, curC }); } } else { int sum = curA + curB; int tmpA = curA + curB; int tmpB = 0; if (chk[tmpA][tmpB][curC] == 0) { chk[tmpA][tmpB][curC] = 1; q.push({ tmpA, tmpB, curC }); } } //B->C if (curC + curB > maxC) { int sum = curA + curC; int tmpC = maxC; int tmpB = sum - tmpC; if (chk[curA][tmpB][tmpC] == 0) { chk[curA][tmpB][tmpC] = 1; q.push({ curA, tmpB, tmpC }); } } else { int sum = curB + curC; int tmpC = curC + curB; int tmpB = 0; if (chk[curA][tmpB][tmpC] == 0) { chk[curA][tmpB][tmpC] = 1; q.push({ curA, tmpB, tmpC }); } } //C->A if (curA + curC > maxA) { int sum = curA + curC; int tmpA = maxA; int tmpC = sum - tmpA; if (chk[tmpA][curB][tmpC] == 0) { chk[tmpA][curB][tmpC] = 1; q.push({ tmpA, curB, tmpC }); } } else { int sum = curA + curC; int tmpA = curA + curC; int tmpC = 0; if (chk[tmpA][curB][tmpC] == 0) { chk[tmpA][curB][tmpC] = 1; q.push({ tmpA, curB, tmpC }); } } //C->B if (curC + curB > maxB) { int sum = curB + curC; int tmpB = maxB; int tmpC = sum - tmpB; if (chk[curA][tmpB][tmpC] == 0) { chk[curA][tmpB][tmpC] = 1; q.push({ curA, tmpB, tmpC }); } } else { int sum = curC + curB; int tmpB = curC + curB; int tmpC = 0; if (chk[curA][tmpB][tmpC] == 0) { chk[curA][tmpB][tmpC] = 1; q.push({ curA, tmpB, tmpC }); } } } } int main() { int maxA, maxB, maxC; scanf("%d %d %d", &maxA, &maxB, &maxC); bfs(maxA, maxB, maxC); sort(rstVec.begin(), rstVec.end()); for (int i = 0; i < rstVec.size(); i++) { printf("%d ", rstVec[i]); } } | cs |
코드가 징그럽게 길다
봉사활동 끝나자마자 고쳐야겠다
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 | #include <stdio.h> #include <vector> #include <queue> #include <algorithm> using namespace std; vector<int> rstVec; typedef struct _cur { int a; int b; int c; }cur; queue<cur> q; int chk[201][201][201] = { 0 }; void pour(int cur1, int cur2, int cur3, int maxW) { if (cur1 + cur2 > maxW) { int sum = cur1 + cur2; int tmp2 = maxW; int tmp1 = sum - tmp2; if (chk[tmp1][tmp2][cur3] == 0) { chk[tmp1][tmp2][cur3] = 1; q.push({ tmp1, tmp2, cur3 }); } } else { int sum = cur1 + cur2; int tmp2 = cur1 + cur2; int tmp1 = 0; if (chk[tmp1][tmp2][cur3] == 0) { chk[tmp1][tmp2][cur3] = 1; q.push({ tmp1, tmp2, cur3 }); } } } void bfs(int maxA, int maxB, int maxC) { q.push({ 0,0,maxC }); chk[0][0][maxC] = 1; while (!q.empty()) { int curA = q.front().a; int curB = q.front().b; int curC = q.front().c; q.pop(); if (curA == 0) { rstVec.push_back(curC); } //A->B pour(curA, curB, curC, maxB); //A->C pour(curA, curC, curB, maxC); //B->A pour(curB, curA, curC, maxA); //B->C pour(curB, curC, curA, maxC); //C->A pour(curC, curA, curB, maxA); //C->B pour(curC, curB, curA, maxB); } } int main() { int maxA, maxB, maxC; scanf("%d %d %d", &maxA, &maxB, &maxC); bfs(maxA, maxB, maxC); sort(rstVec.begin(), rstVec.end()); for (int i = 1; i < rstVec.size(); i++) { printf("%d ", rstVec[i]); } } | cs |
고쳤다. 이제야 보기 편하네
'알고리즘 > BFS' 카테고리의 다른 글
| 1953 팀배분 (0) | 2020.01.20 |
|---|---|
| 3184 양 (0) | 2020.01.20 |
| 12761 돌다리 (0) | 2020.01.20 |
| 9372 상근이의 여행 (0) | 2020.01.20 |
| 5014 스타트링크 (0) | 2020.01.20 |