08_backtracking.c

Download
c 359 lines 10.1 KB 
  1/*
  2 * ๋ฐฑํŠธ๋ž˜ํ‚น (Backtracking)
  3 * N-Queens, Permutations, Combinations, Sudoku
  4 *
  5 * ๋ชจ๋“  ๊ฐ€๋Šฅ์„ฑ์„ ํƒ์ƒ‰ํ•˜๋˜ ๋ถˆํ•„์š”ํ•œ ๊ฒฝ๋กœ๋Š” ๊ฐ€์ง€์น˜๊ธฐํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11#include <string.h>
 12
 13/* =============================================================================
 14 * 1. N-Queens ๋ฌธ์ œ
 15 * ============================================================================= */
 16
 17bool is_safe(int board[], int row, int col, int n) {
 18    for (int i = 0; i < row; i++) {
 19        /* ๊ฐ™์€ ์—ด */
 20        if (board[i] == col)
 21            return false;
 22        /* ๋Œ€๊ฐ์„  */
 23        if (abs(board[i] - col) == abs(i - row))
 24            return false;
 25    }
 26    return true;
 27}
 28
 29void print_queens_board(int board[], int n) {
 30    for (int i = 0; i < n; i++) {
 31        printf("      ");
 32        for (int j = 0; j < n; j++) {
 33            printf("%c ", board[i] == j ? 'Q' : '.');
 34        }
 35        printf("\n");
 36    }
 37}
 38
 39int solve_queens(int board[], int row, int n, int print_solutions) {
 40    if (row == n) {
 41        if (print_solutions) {
 42            printf("    ํ•ด:\n");
 43            print_queens_board(board, n);
 44        }
 45        return 1;
 46    }
 47
 48    int count = 0;
 49    for (int col = 0; col < n; col++) {
 50        if (is_safe(board, row, col, n)) {
 51            board[row] = col;
 52            count += solve_queens(board, row + 1, n, print_solutions);
 53            board[row] = -1;  /* ๋ฐฑํŠธ๋ž˜ํ‚น */
 54        }
 55    }
 56
 57    return count;
 58}
 59
 60int n_queens(int n, int print_solutions) {
 61    int* board = malloc(n * sizeof(int));
 62    for (int i = 0; i < n; i++) board[i] = -1;
 63
 64    int count = solve_queens(board, 0, n, print_solutions);
 65    free(board);
 66    return count;
 67}
 68
 69/* =============================================================================
 70 * 2. ์ˆœ์—ด (Permutations)
 71 * ============================================================================= */
 72
 73void swap(int* a, int* b) {
 74    int temp = *a;
 75    *a = *b;
 76    *b = temp;
 77}
 78
 79void permute_impl(int arr[], int start, int end, int* count) {
 80    if (start == end) {
 81        (*count)++;
 82        printf("      [");
 83        for (int i = 0; i <= end; i++) {
 84            printf("%d", arr[i]);
 85            if (i < end) printf(", ");
 86        }
 87        printf("]\n");
 88        return;
 89    }
 90
 91    for (int i = start; i <= end; i++) {
 92        swap(&arr[start], &arr[i]);
 93        permute_impl(arr, start + 1, end, count);
 94        swap(&arr[start], &arr[i]);  /* ๋ฐฑํŠธ๋ž˜ํ‚น */
 95    }
 96}
 97
 98int permutations(int arr[], int n) {
 99    int count = 0;
100    permute_impl(arr, 0, n - 1, &count);
101    return count;
102}
103
104/* =============================================================================
105 * 3. ์กฐํ•ฉ (Combinations)
106 * ============================================================================= */
107
108void combine_impl(int n, int k, int start, int* current, int idx, int* count) {
109    if (idx == k) {
110        (*count)++;
111        printf("      [");
112        for (int i = 0; i < k; i++) {
113            printf("%d", current[i]);
114            if (i < k - 1) printf(", ");
115        }
116        printf("]\n");
117        return;
118    }
119
120    for (int i = start; i <= n; i++) {
121        current[idx] = i;
122        combine_impl(n, k, i + 1, current, idx + 1, count);
123    }
124}
125
126int combinations(int n, int k) {
127    int* current = malloc(k * sizeof(int));
128    int count = 0;
129    combine_impl(n, k, 1, current, 0, &count);
130    free(current);
131    return count;
132}
133
134/* =============================================================================
135 * 4. ๋ถ€๋ถ„์ง‘ํ•ฉ (Subsets)
136 * ============================================================================= */
137
138void subsets_impl(int arr[], int n, int* current, int current_size, int index) {
139    /* ํ˜„์žฌ ๋ถ€๋ถ„์ง‘ํ•ฉ ์ถœ๋ ฅ */
140    printf("      {");
141    for (int i = 0; i < current_size; i++) {
142        printf("%d", current[i]);
143        if (i < current_size - 1) printf(", ");
144    }
145    printf("}\n");
146
147    for (int i = index; i < n; i++) {
148        current[current_size] = arr[i];
149        subsets_impl(arr, n, current, current_size + 1, i + 1);
150    }
151}
152
153void subsets(int arr[], int n) {
154    int* current = malloc(n * sizeof(int));
155    subsets_impl(arr, n, current, 0, 0);
156    free(current);
157}
158
159/* =============================================================================
160 * 5. ์Šค๋„์ฟ  ํ•ด๊ฒฐ
161 * ============================================================================= */
162
163#define SUDOKU_SIZE 9
164
165bool is_valid_sudoku(int board[9][9], int row, int col, int num) {
166    /* ํ–‰ ๊ฒ€์‚ฌ */
167    for (int x = 0; x < 9; x++) {
168        if (board[row][x] == num) return false;
169    }
170
171    /* ์—ด ๊ฒ€์‚ฌ */
172    for (int x = 0; x < 9; x++) {
173        if (board[x][col] == num) return false;
174    }
175
176    /* 3x3 ๋ฐ•์Šค ๊ฒ€์‚ฌ */
177    int start_row = row - row % 3;
178    int start_col = col - col % 3;
179    for (int i = 0; i < 3; i++) {
180        for (int j = 0; j < 3; j++) {
181            if (board[start_row + i][start_col + j] == num)
182                return false;
183        }
184    }
185
186    return true;
187}
188
189bool solve_sudoku(int board[9][9]) {
190    for (int row = 0; row < 9; row++) {
191        for (int col = 0; col < 9; col++) {
192            if (board[row][col] == 0) {
193                for (int num = 1; num <= 9; num++) {
194                    if (is_valid_sudoku(board, row, col, num)) {
195                        board[row][col] = num;
196                        if (solve_sudoku(board))
197                            return true;
198                        board[row][col] = 0;  /* ๋ฐฑํŠธ๋ž˜ํ‚น */
199                    }
200                }
201                return false;  /* ๊ฐ€๋Šฅํ•œ ์ˆซ์ž ์—†์Œ */
202            }
203        }
204    }
205    return true;  /* ๋ชจ๋“  ์นธ ์ฑ„์›€ */
206}
207
208void print_sudoku(int board[9][9]) {
209    for (int i = 0; i < 9; i++) {
210        if (i % 3 == 0 && i != 0)
211            printf("      ------+-------+------\n");
212        printf("      ");
213        for (int j = 0; j < 9; j++) {
214            if (j % 3 == 0 && j != 0) printf("| ");
215            printf("%d ", board[i][j]);
216        }
217        printf("\n");
218    }
219}
220
221/* =============================================================================
222 * 6. ๋ฌธ์ž์—ด ์ˆœ์—ด
223 * ============================================================================= */
224
225void string_permute(char str[], int start, int end) {
226    if (start == end) {
227        printf("      %s\n", str);
228        return;
229    }
230
231    for (int i = start; i <= end; i++) {
232        char temp = str[start];
233        str[start] = str[i];
234        str[i] = temp;
235
236        string_permute(str, start + 1, end);
237
238        temp = str[start];
239        str[start] = str[i];
240        str[i] = temp;
241    }
242}
243
244/* =============================================================================
245 * 7. ํ•ฉ์ด target์ธ ์กฐํ•ฉ
246 * ============================================================================= */
247
248void combination_sum_impl(int candidates[], int n, int target, int start,
249                          int* current, int current_size, int* count) {
250    if (target == 0) {
251        (*count)++;
252        printf("      [");
253        for (int i = 0; i < current_size; i++) {
254            printf("%d", current[i]);
255            if (i < current_size - 1) printf(", ");
256        }
257        printf("]\n");
258        return;
259    }
260
261    for (int i = start; i < n; i++) {
262        if (candidates[i] > target) break;
263
264        current[current_size] = candidates[i];
265        combination_sum_impl(candidates, n, target - candidates[i],
266                            i, current, current_size + 1, count);
267    }
268}
269
270int combination_sum(int candidates[], int n, int target) {
271    int* current = malloc(target * sizeof(int));
272    int count = 0;
273    combination_sum_impl(candidates, n, target, 0, current, 0, &count);
274    free(current);
275    return count;
276}
277
278/* =============================================================================
279 * ํ…Œ์ŠคํŠธ
280 * ============================================================================= */
281
282int main(void) {
283    printf("============================================================\n");
284    printf("๋ฐฑํŠธ๋ž˜ํ‚น (Backtracking) ์˜ˆ์ œ\n");
285    printf("============================================================\n");
286
287    /* 1. N-Queens */
288    printf("\n[1] N-Queens ๋ฌธ์ œ\n");
289    printf("    4-Queens ํ•ด:\n");
290    int solutions_4 = n_queens(4, 1);
291    printf("    4-Queens ํ•ด ๊ฐœ์ˆ˜: %d\n", solutions_4);
292    printf("    8-Queens ํ•ด ๊ฐœ์ˆ˜: %d\n", n_queens(8, 0));
293
294    /* 2. ์ˆœ์—ด */
295    printf("\n[2] ์ˆœ์—ด\n");
296    int arr2[] = {1, 2, 3};
297    printf("    [1, 2, 3]์˜ ์ˆœ์—ด:\n");
298    int perm_count = permutations(arr2, 3);
299    printf("    ์ด %d๊ฐœ\n", perm_count);
300
301    /* 3. ์กฐํ•ฉ */
302    printf("\n[3] ์กฐํ•ฉ\n");
303    printf("    C(4, 2):\n");
304    int comb_count = combinations(4, 2);
305    printf("    ์ด %d๊ฐœ\n", comb_count);
306
307    /* 4. ๋ถ€๋ถ„์ง‘ํ•ฉ */
308    printf("\n[4] ๋ถ€๋ถ„์ง‘ํ•ฉ\n");
309    int arr4[] = {1, 2, 3};
310    printf("    {1, 2, 3}์˜ ๋ถ€๋ถ„์ง‘ํ•ฉ:\n");
311    subsets(arr4, 3);
312
313    /* 5. ์Šค๋„์ฟ  */
314    printf("\n[5] ์Šค๋„์ฟ  ํ•ด๊ฒฐ\n");
315    int sudoku[9][9] = {
316        {5, 3, 0, 0, 7, 0, 0, 0, 0},
317        {6, 0, 0, 1, 9, 5, 0, 0, 0},
318        {0, 9, 8, 0, 0, 0, 0, 6, 0},
319        {8, 0, 0, 0, 6, 0, 0, 0, 3},
320        {4, 0, 0, 8, 0, 3, 0, 0, 1},
321        {7, 0, 0, 0, 2, 0, 0, 0, 6},
322        {0, 6, 0, 0, 0, 0, 2, 8, 0},
323        {0, 0, 0, 4, 1, 9, 0, 0, 5},
324        {0, 0, 0, 0, 8, 0, 0, 7, 9}
325    };
326
327    printf("    ์ดˆ๊ธฐ ์ƒํƒœ:\n");
328    print_sudoku(sudoku);
329
330    if (solve_sudoku(sudoku)) {
331        printf("\n    ํ•ด๊ฒฐ:\n");
332        print_sudoku(sudoku);
333    }
334
335    /* 6. ๋ฌธ์ž์—ด ์ˆœ์—ด */
336    printf("\n[6] ๋ฌธ์ž์—ด ์ˆœ์—ด\n");
337    char str[] = "ABC";
338    printf("    'ABC'์˜ ์ˆœ์—ด:\n");
339    string_permute(str, 0, 2);
340
341    /* 7. ํ•ฉ์ด target์ธ ์กฐํ•ฉ */
342    printf("\n[7] ํ•ฉ์ด target์ธ ์กฐํ•ฉ\n");
343    int candidates[] = {2, 3, 6, 7};
344    printf("    [2,3,6,7], target=7:\n");
345    combination_sum(candidates, 4, 7);
346
347    /* 8. ๋ฐฑํŠธ๋ž˜ํ‚น ์š”์•ฝ */
348    printf("\n[8] ๋ฐฑํŠธ๋ž˜ํ‚น ํŒจํ„ด\n");
349    printf("    1. ํ•ด๋‹ต ๊ฒ€์‚ฌ (base case)\n");
350    printf("    2. ํ›„๋ณด ์ƒ์„ฑ\n");
351    printf("    3. ์œ ๋ง์„ฑ ๊ฒ€์‚ฌ (๊ฐ€์ง€์น˜๊ธฐ)\n");
352    printf("    4. ์žฌ๊ท€ ํ˜ธ์ถœ\n");
353    printf("    5. ์ƒํƒœ ๋ณต์› (๋ฐฑํŠธ๋ž˜ํ‚น)\n");
354
355    printf("\n============================================================\n");
356
357    return 0;
358}