08_backtracking.cpp

Download
cpp 406 lines 11.4 KB 
  1/*
  2 * ๋ฐฑํŠธ๋ž˜ํ‚น (Backtracking)
  3 * N-Queens, Permutations, Combinations, Sudoku
  4 *
  5 * ๋ชจ๋“  ๊ฐ€๋Šฅ์„ฑ์„ ํƒ์ƒ‰ํ•˜๋˜ ๋ถˆํ•„์š”ํ•œ ๊ฒฝ๋กœ๋ฅผ ๊ฐ€์ง€์น˜๊ธฐํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <string>
 11#include <algorithm>
 12
 13using namespace std;
 14
 15// =============================================================================
 16// 1. N-Queens
 17// =============================================================================
 18
 19class NQueens {
 20private:
 21    int n;
 22    vector<vector<string>> solutions;
 23
 24    bool isSafe(vector<string>& board, int row, int col) {
 25        // ๊ฐ™์€ ์—ด ๊ฒ€์‚ฌ
 26        for (int i = 0; i < row; i++) {
 27            if (board[i][col] == 'Q') return false;
 28        }
 29
 30        // ์™ผ์ชฝ ์œ„ ๋Œ€๊ฐ์„ 
 31        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
 32            if (board[i][j] == 'Q') return false;
 33        }
 34
 35        // ์˜ค๋ฅธ์ชฝ ์œ„ ๋Œ€๊ฐ์„ 
 36        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
 37            if (board[i][j] == 'Q') return false;
 38        }
 39
 40        return true;
 41    }
 42
 43    void solve(vector<string>& board, int row) {
 44        if (row == n) {
 45            solutions.push_back(board);
 46            return;
 47        }
 48
 49        for (int col = 0; col < n; col++) {
 50            if (isSafe(board, row, col)) {
 51                board[row][col] = 'Q';
 52                solve(board, row + 1);
 53                board[row][col] = '.';
 54            }
 55        }
 56    }
 57
 58public:
 59    vector<vector<string>> solveNQueens(int n) {
 60        this->n = n;
 61        solutions.clear();
 62        vector<string> board(n, string(n, '.'));
 63        solve(board, 0);
 64        return solutions;
 65    }
 66};
 67
 68// =============================================================================
 69// 2. ์ˆœ์—ด (Permutations)
 70// =============================================================================
 71
 72class Permutations {
 73private:
 74    vector<vector<int>> result;
 75
 76    void backtrack(vector<int>& nums, int start) {
 77        if (start == (int)nums.size()) {
 78            result.push_back(nums);
 79            return;
 80        }
 81
 82        for (int i = start; i < (int)nums.size(); i++) {
 83            swap(nums[start], nums[i]);
 84            backtrack(nums, start + 1);
 85            swap(nums[start], nums[i]);
 86        }
 87    }
 88
 89public:
 90    vector<vector<int>> permute(vector<int>& nums) {
 91        result.clear();
 92        backtrack(nums, 0);
 93        return result;
 94    }
 95};
 96
 97// ์ค‘๋ณต ์žˆ๋Š” ์ˆœ์—ด
 98class PermutationsUnique {
 99private:
100    vector<vector<int>> result;
101
102    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& current) {
103        if (current.size() == nums.size()) {
104            result.push_back(current);
105            return;
106        }
107
108        for (int i = 0; i < (int)nums.size(); i++) {
109            if (used[i]) continue;
110            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
111
112            used[i] = true;
113            current.push_back(nums[i]);
114            backtrack(nums, used, current);
115            current.pop_back();
116            used[i] = false;
117        }
118    }
119
120public:
121    vector<vector<int>> permuteUnique(vector<int>& nums) {
122        result.clear();
123        sort(nums.begin(), nums.end());
124        vector<bool> used(nums.size(), false);
125        vector<int> current;
126        backtrack(nums, used, current);
127        return result;
128    }
129};
130
131// =============================================================================
132// 3. ์กฐํ•ฉ (Combinations)
133// =============================================================================
134
135class Combinations {
136private:
137    vector<vector<int>> result;
138
139    void backtrack(int n, int k, int start, vector<int>& current) {
140        if ((int)current.size() == k) {
141            result.push_back(current);
142            return;
143        }
144
145        // ๊ฐ€์ง€์น˜๊ธฐ: ๋‚จ์€ ์›์†Œ๊ฐ€ ๋ถ€์กฑํ•˜๋ฉด ์ค‘๋‹จ
146        for (int i = start; i <= n - (k - (int)current.size()) + 1; i++) {
147            current.push_back(i);
148            backtrack(n, k, i + 1, current);
149            current.pop_back();
150        }
151    }
152
153public:
154    vector<vector<int>> combine(int n, int k) {
155        result.clear();
156        vector<int> current;
157        backtrack(n, k, 1, current);
158        return result;
159    }
160};
161
162// ํ•ฉ์ด target์ธ ์กฐํ•ฉ
163class CombinationSum {
164private:
165    vector<vector<int>> result;
166
167    void backtrack(vector<int>& candidates, int target, int start, vector<int>& current) {
168        if (target == 0) {
169            result.push_back(current);
170            return;
171        }
172
173        for (int i = start; i < (int)candidates.size() && candidates[i] <= target; i++) {
174            current.push_back(candidates[i]);
175            backtrack(candidates, target - candidates[i], i, current);  // ๊ฐ™์€ ์›์†Œ ์žฌ์‚ฌ์šฉ ๊ฐ€๋Šฅ
176            current.pop_back();
177        }
178    }
179
180public:
181    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
182        result.clear();
183        sort(candidates.begin(), candidates.end());
184        vector<int> current;
185        backtrack(candidates, target, 0, current);
186        return result;
187    }
188};
189
190// =============================================================================
191// 4. ๋ถ€๋ถ„์ง‘ํ•ฉ (Subsets)
192// =============================================================================
193
194class Subsets {
195private:
196    vector<vector<int>> result;
197
198    void backtrack(vector<int>& nums, int start, vector<int>& current) {
199        result.push_back(current);
200
201        for (int i = start; i < (int)nums.size(); i++) {
202            current.push_back(nums[i]);
203            backtrack(nums, i + 1, current);
204            current.pop_back();
205        }
206    }
207
208public:
209    vector<vector<int>> subsets(vector<int>& nums) {
210        result.clear();
211        vector<int> current;
212        backtrack(nums, 0, current);
213        return result;
214    }
215};
216
217// =============================================================================
218// 5. ์Šค๋„์ฟ 
219// =============================================================================
220
221class Sudoku {
222private:
223    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
224        for (int i = 0; i < 9; i++) {
225            if (board[row][i] == c) return false;
226            if (board[i][col] == c) return false;
227            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
228        }
229        return true;
230    }
231
232    bool solve(vector<vector<char>>& board) {
233        for (int i = 0; i < 9; i++) {
234            for (int j = 0; j < 9; j++) {
235                if (board[i][j] == '.') {
236                    for (char c = '1'; c <= '9'; c++) {
237                        if (isValid(board, i, j, c)) {
238                            board[i][j] = c;
239                            if (solve(board)) return true;
240                            board[i][j] = '.';
241                        }
242                    }
243                    return false;
244                }
245            }
246        }
247        return true;
248    }
249
250public:
251    void solveSudoku(vector<vector<char>>& board) {
252        solve(board);
253    }
254};
255
256// =============================================================================
257// 6. ๋‹จ์–ด ๊ฒ€์ƒ‰ (Word Search)
258// =============================================================================
259
260class WordSearch {
261private:
262    int rows, cols;
263    int dx[4] = {0, 0, 1, -1};
264    int dy[4] = {1, -1, 0, 0};
265
266    bool dfs(vector<vector<char>>& board, const string& word, int idx, int r, int c) {
267        if (idx == (int)word.size()) return true;
268        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
269        if (board[r][c] != word[idx]) return false;
270
271        char temp = board[r][c];
272        board[r][c] = '#';  // ๋ฐฉ๋ฌธ ํ‘œ์‹œ
273
274        for (int d = 0; d < 4; d++) {
275            if (dfs(board, word, idx + 1, r + dx[d], c + dy[d])) {
276                board[r][c] = temp;
277                return true;
278            }
279        }
280
281        board[r][c] = temp;
282        return false;
283    }
284
285public:
286    bool exist(vector<vector<char>>& board, const string& word) {
287        rows = board.size();
288        cols = board[0].size();
289
290        for (int i = 0; i < rows; i++) {
291            for (int j = 0; j < cols; j++) {
292                if (dfs(board, word, 0, i, j)) return true;
293            }
294        }
295        return false;
296    }
297};
298
299// =============================================================================
300// ํ…Œ์ŠคํŠธ
301// =============================================================================
302
303void printVector(const vector<int>& v) {
304    cout << "[";
305    for (size_t i = 0; i < v.size(); i++) {
306        cout << v[i];
307        if (i < v.size() - 1) cout << ",";
308    }
309    cout << "]";
310}
311
312int main() {
313    cout << "============================================================" << endl;
314    cout << "๋ฐฑํŠธ๋ž˜ํ‚น ์˜ˆ์ œ" << endl;
315    cout << "============================================================" << endl;
316
317    // 1. N-Queens
318    cout << "\n[1] N-Queens" << endl;
319    NQueens nq;
320    auto queens = nq.solveNQueens(4);
321    cout << "    4-Queens ํ•ด์˜ ๊ฐœ์ˆ˜: " << queens.size() << endl;
322    if (!queens.empty()) {
323        cout << "    ์ฒซ ๋ฒˆ์งธ ํ•ด:" << endl;
324        for (const auto& row : queens[0]) {
325            cout << "      " << row << endl;
326        }
327    }
328
329    // 2. ์ˆœ์—ด
330    cout << "\n[2] ์ˆœ์—ด" << endl;
331    vector<int> nums = {1, 2, 3};
332    Permutations perm;
333    auto perms = perm.permute(nums);
334    cout << "    [1,2,3]์˜ ์ˆœ์—ด (" << perms.size() << "๊ฐœ):" << endl;
335    cout << "    ";
336    for (const auto& p : perms) {
337        printVector(p);
338        cout << " ";
339    }
340    cout << endl;
341
342    // 3. ์กฐํ•ฉ
343    cout << "\n[3] ์กฐํ•ฉ" << endl;
344    Combinations comb;
345    auto combs = comb.combine(4, 2);
346    cout << "    C(4,2) (" << combs.size() << "๊ฐœ):" << endl;
347    cout << "    ";
348    for (const auto& c : combs) {
349        printVector(c);
350        cout << " ";
351    }
352    cout << endl;
353
354    // 4. ์กฐํ•ฉ ํ•ฉ
355    cout << "\n[4] ์กฐํ•ฉ ํ•ฉ" << endl;
356    vector<int> candidates = {2, 3, 6, 7};
357    CombinationSum cs;
358    auto combSums = cs.combinationSum(candidates, 7);
359    cout << "    [2,3,6,7], target=7:" << endl;
360    cout << "    ";
361    for (const auto& c : combSums) {
362        printVector(c);
363        cout << " ";
364    }
365    cout << endl;
366
367    // 5. ๋ถ€๋ถ„์ง‘ํ•ฉ
368    cout << "\n[5] ๋ถ€๋ถ„์ง‘ํ•ฉ" << endl;
369    vector<int> nums2 = {1, 2, 3};
370    Subsets sub;
371    auto subs = sub.subsets(nums2);
372    cout << "    [1,2,3]์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ (" << subs.size() << "๊ฐœ):" << endl;
373    cout << "    ";
374    for (const auto& s : subs) {
375        printVector(s);
376        cout << " ";
377    }
378    cout << endl;
379
380    // 6. ๋‹จ์–ด ๊ฒ€์ƒ‰
381    cout << "\n[6] ๋‹จ์–ด ๊ฒ€์ƒ‰" << endl;
382    vector<vector<char>> board = {
383        {'A', 'B', 'C', 'E'},
384        {'S', 'F', 'C', 'S'},
385        {'A', 'D', 'E', 'E'}
386    };
387    WordSearch ws;
388    cout << "    \"ABCCED\": " << (ws.exist(board, "ABCCED") ? "์žˆ์Œ" : "์—†์Œ") << endl;
389    cout << "    \"SEE\": " << (ws.exist(board, "SEE") ? "์žˆ์Œ" : "์—†์Œ") << endl;
390    cout << "    \"ABCB\": " << (ws.exist(board, "ABCB") ? "์žˆ์Œ" : "์—†์Œ") << endl;
391
392    // 7. ๋ณต์žก๋„ ์š”์•ฝ
393    cout << "\n[7] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
394    cout << "    | ๋ฌธ์ œ           | ์‹œ๊ฐ„๋ณต์žก๋„    |" << endl;
395    cout << "    |----------------|---------------|" << endl;
396    cout << "    | N-Queens       | O(N!)         |" << endl;
397    cout << "    | ์ˆœ์—ด           | O(N!)         |" << endl;
398    cout << "    | ์กฐํ•ฉ C(n,k)    | O(C(n,k))     |" << endl;
399    cout << "    | ๋ถ€๋ถ„์ง‘ํ•ฉ       | O(2^N)        |" << endl;
400    cout << "    | ์Šค๋„์ฟ          | O(9^(๋นˆ์นธ์ˆ˜)) |" << endl;
401
402    cout << "\n============================================================" << endl;
403
404    return 0;
405}