1"""
2๋ฐฑํธ๋ํน (Backtracking)
3Backtracking Algorithms
4
5ํด๋ฅผ ์ฐพ๋ ๋์ค ๋งํ๋ฉด ๋๋์๊ฐ์ ๋ค์ ํด๋ฅผ ์ฐพ๋ ๊ธฐ๋ฒ์
๋๋ค.
6์์ ํ์์ ํจ์จ์ ์ผ๋ก ์ํํ ์ ์์ต๋๋ค.
7"""
8
9from typing import List
10
11
12# =============================================================================
13# 1. ์์ด (Permutations)
14# =============================================================================
15def permutations(nums: List[int]) -> List[List[int]]:
16 """
17 ๋ฐฐ์ด์ ๋ชจ๋ ์์ด ์์ฑ
18 ์๊ฐ๋ณต์ก๋: O(n! * n)
19 """
20 result = []
21
22 def backtrack(path, remaining):
23 if not remaining:
24 result.append(path[:])
25 return
26
27 for i in range(len(remaining)):
28 path.append(remaining[i])
29 backtrack(path, remaining[:i] + remaining[i + 1:])
30 path.pop()
31
32 backtrack([], nums)
33 return result
34
35
36def permutations_inplace(nums: List[int]) -> List[List[int]]:
37 """์์ด (swap ๋ฐฉ์)"""
38 result = []
39
40 def backtrack(start):
41 if start == len(nums):
42 result.append(nums[:])
43 return
44
45 for i in range(start, len(nums)):
46 nums[start], nums[i] = nums[i], nums[start]
47 backtrack(start + 1)
48 nums[start], nums[i] = nums[i], nums[start]
49
50 backtrack(0)
51 return result
52
53
54# =============================================================================
55# 2. ์กฐํฉ (Combinations)
56# =============================================================================
57def combinations(n: int, k: int) -> List[List[int]]:
58 """
59 1~n์์ k๊ฐ๋ฅผ ์ ํํ๋ ๋ชจ๋ ์กฐํฉ
60 ์๊ฐ๋ณต์ก๋: O(C(n,k) * k)
61 """
62 result = []
63
64 def backtrack(start, path):
65 if len(path) == k:
66 result.append(path[:])
67 return
68
69 # ๋จ์ ์ซ์๊ฐ ๋ถ์กฑํ๋ฉด ๊ฐ์ง์น๊ธฐ
70 need = k - len(path)
71 available = n - start + 1
72 if available < need:
73 return
74
75 for i in range(start, n + 1):
76 path.append(i)
77 backtrack(i + 1, path)
78 path.pop()
79
80 backtrack(1, [])
81 return result
82
83
84def combination_sum(candidates: List[int], target: int) -> List[List[int]]:
85 """
86 ํฉ์ด target์ธ ์กฐํฉ ์ฐพ๊ธฐ (๊ฐ์ ์ซ์ ์ฌ๋ฌ ๋ฒ ์ฌ์ฉ ๊ฐ๋ฅ)
87 """
88 result = []
89 candidates.sort()
90
91 def backtrack(start, path, remaining):
92 if remaining == 0:
93 result.append(path[:])
94 return
95 if remaining < 0:
96 return
97
98 for i in range(start, len(candidates)):
99 if candidates[i] > remaining:
100 break
101 path.append(candidates[i])
102 backtrack(i, path, remaining - candidates[i]) # i๋ถํฐ (์ค๋ณต ํ์ฉ)
103 path.pop()
104
105 backtrack(0, [], target)
106 return result
107
108
109# =============================================================================
110# 3. ๋ถ๋ถ ์งํฉ (Subsets)
111# =============================================================================
112def subsets(nums: List[int]) -> List[List[int]]:
113 """
114 ๋ฐฐ์ด์ ๋ชจ๋ ๋ถ๋ถ ์งํฉ
115 ์๊ฐ๋ณต์ก๋: O(2^n * n)
116 """
117 result = []
118
119 def backtrack(start, path):
120 result.append(path[:])
121
122 for i in range(start, len(nums)):
123 path.append(nums[i])
124 backtrack(i + 1, path)
125 path.pop()
126
127 backtrack(0, [])
128 return result
129
130
131def subsets_with_dup(nums: List[int]) -> List[List[int]]:
132 """์ค๋ณต ์์๊ฐ ์๋ ๋ฐฐ์ด์ ๋ชจ๋ ๋ถ๋ถ ์งํฉ"""
133 result = []
134 nums.sort()
135
136 def backtrack(start, path):
137 result.append(path[:])
138
139 for i in range(start, len(nums)):
140 # ๊ฐ์ ๋ ๋ฒจ์์ ์ค๋ณต ๊ฑด๋๋ฐ๊ธฐ
141 if i > start and nums[i] == nums[i - 1]:
142 continue
143 path.append(nums[i])
144 backtrack(i + 1, path)
145 path.pop()
146
147 backtrack(0, [])
148 return result
149
150
151# =============================================================================
152# 4. N-Queens ๋ฌธ์
153# =============================================================================
154def solve_n_queens(n: int) -> List[List[str]]:
155 """
156 N-Queens: n x n ์ฒด์คํ์ n๊ฐ์ ํธ์ ์๋ก ๊ณต๊ฒฉํ์ง ์๊ฒ ๋ฐฐ์น
157 """
158 result = []
159 board = [['.'] * n for _ in range(n)]
160
161 # ์ด, ๋๊ฐ์ ์ฒดํฌ์ฉ ์งํฉ
162 cols = set()
163 diag1 = set() # row - col
164 diag2 = set() # row + col
165
166 def backtrack(row):
167 if row == n:
168 result.append([''.join(r) for r in board])
169 return
170
171 for col in range(n):
172 if col in cols or (row - col) in diag1 or (row + col) in diag2:
173 continue
174
175 # ํธ ๋ฐฐ์น
176 board[row][col] = 'Q'
177 cols.add(col)
178 diag1.add(row - col)
179 diag2.add(row + col)
180
181 backtrack(row + 1)
182
183 # ๋ณต์
184 board[row][col] = '.'
185 cols.remove(col)
186 diag1.remove(row - col)
187 diag2.remove(row + col)
188
189 backtrack(0)
190 return result
191
192
193def count_n_queens(n: int) -> int:
194 """N-Queens ํด์ ๊ฐ์๋ง ์นด์ดํธ"""
195 count = [0]
196 cols = set()
197 diag1 = set()
198 diag2 = set()
199
200 def backtrack(row):
201 if row == n:
202 count[0] += 1
203 return
204
205 for col in range(n):
206 if col in cols or (row - col) in diag1 or (row + col) in diag2:
207 continue
208
209 cols.add(col)
210 diag1.add(row - col)
211 diag2.add(row + col)
212
213 backtrack(row + 1)
214
215 cols.remove(col)
216 diag1.remove(row - col)
217 diag2.remove(row + col)
218
219 backtrack(0)
220 return count[0]
221
222
223# =============================================================================
224# 5. ์ค๋์ฟ ํ๊ธฐ
225# =============================================================================
226def solve_sudoku(board: List[List[str]]) -> bool:
227 """
228 9x9 ์ค๋์ฟ ํ๊ธฐ (in-place)
229 ์ฑ๊ณตํ๋ฉด True ๋ฐํ
230 """
231 def is_valid(row, col, num):
232 # ํ ์ฒดํฌ
233 if num in board[row]:
234 return False
235
236 # ์ด ์ฒดํฌ
237 for r in range(9):
238 if board[r][col] == num:
239 return False
240
241 # 3x3 ๋ฐ์ค ์ฒดํฌ
242 box_row, box_col = 3 * (row // 3), 3 * (col // 3)
243 for r in range(box_row, box_row + 3):
244 for c in range(box_col, box_col + 3):
245 if board[r][c] == num:
246 return False
247
248 return True
249
250 def backtrack():
251 for row in range(9):
252 for col in range(9):
253 if board[row][col] == '.':
254 for num in '123456789':
255 if is_valid(row, col, num):
256 board[row][col] = num
257 if backtrack():
258 return True
259 board[row][col] = '.'
260 return False
261 return True
262
263 return backtrack()
264
265
266# =============================================================================
267# 6. ๋จ์ด ๊ฒ์ (Word Search)
268# =============================================================================
269def word_search(board: List[List[str]], word: str) -> bool:
270 """
271 2D ๊ทธ๋ฆฌ๋์์ ๋จ์ด ์ฐพ๊ธฐ (์ธ์ ์นธ์ผ๋ก๋ง ์ด๋)
272 """
273 if not board or not board[0]:
274 return False
275
276 rows, cols = len(board), len(board[0])
277
278 def backtrack(r, c, idx):
279 if idx == len(word):
280 return True
281 if r < 0 or r >= rows or c < 0 or c >= cols:
282 return False
283 if board[r][c] != word[idx]:
284 return False
285
286 # ๋ฐฉ๋ฌธ ํ์
287 temp = board[r][c]
288 board[r][c] = '#'
289
290 # 4๋ฐฉํฅ ํ์
291 found = (backtrack(r + 1, c, idx + 1) or
292 backtrack(r - 1, c, idx + 1) or
293 backtrack(r, c + 1, idx + 1) or
294 backtrack(r, c - 1, idx + 1))
295
296 # ๋ณต์
297 board[r][c] = temp
298
299 return found
300
301 for r in range(rows):
302 for c in range(cols):
303 if backtrack(r, c, 0):
304 return True
305 return False
306
307
308# =============================================================================
309# 7. ๊ดํธ ์์ฑ
310# =============================================================================
311def generate_parentheses(n: int) -> List[str]:
312 """
313 n์์ ์ ํจํ ๊ดํธ ์กฐํฉ ์์ฑ
314 """
315 result = []
316
317 def backtrack(path, open_count, close_count):
318 if len(path) == 2 * n:
319 result.append(''.join(path))
320 return
321
322 if open_count < n:
323 path.append('(')
324 backtrack(path, open_count + 1, close_count)
325 path.pop()
326
327 if close_count < open_count:
328 path.append(')')
329 backtrack(path, open_count, close_count + 1)
330 path.pop()
331
332 backtrack([], 0, 0)
333 return result
334
335
336# =============================================================================
337# ํ
์คํธ
338# =============================================================================
339def main():
340 print("=" * 60)
341 print("๋ฐฑํธ๋ํน (Backtracking) ์์ ")
342 print("=" * 60)
343
344 # 1. ์์ด
345 print("\n[1] ์์ด (Permutations)")
346 nums = [1, 2, 3]
347 perms = permutations(nums)
348 print(f" {nums}์ ์์ด ({len(perms)}๊ฐ):")
349 for p in perms[:6]: # ์ฒ์ 6๊ฐ๋ง
350 print(f" {p}")
351
352 # 2. ์กฐํฉ
353 print("\n[2] ์กฐํฉ (Combinations)")
354 n, k = 4, 2
355 combs = combinations(n, k)
356 print(f" C({n}, {k}) = {len(combs)}๊ฐ:")
357 print(f" {combs}")
358
359 print("\n ์กฐํฉ ํฉ (Combination Sum)")
360 candidates = [2, 3, 6, 7]
361 target = 7
362 result = combination_sum(candidates, target)
363 print(f" {candidates}์์ ํฉ์ด {target}์ธ ์กฐํฉ: {result}")
364
365 # 3. ๋ถ๋ถ ์งํฉ
366 print("\n[3] ๋ถ๋ถ ์งํฉ (Subsets)")
367 nums = [1, 2, 3]
368 subs = subsets(nums)
369 print(f" {nums}์ ๋ถ๋ถ์งํฉ ({len(subs)}๊ฐ): {subs}")
370
371 print("\n ์ค๋ณต ํฌํจ ๋ถ๋ถ ์งํฉ")
372 nums_dup = [1, 2, 2]
373 subs_dup = subsets_with_dup(nums_dup)
374 print(f" {nums_dup}์ ๋ถ๋ถ์งํฉ: {subs_dup}")
375
376 # 4. N-Queens
377 print("\n[4] N-Queens ๋ฌธ์ ")
378 for n in [4, 8]:
379 count = count_n_queens(n)
380 print(f" {n}-Queens ํด์ ๊ฐ์: {count}")
381
382 print("\n 4-Queens ํด ์์:")
383 solutions = solve_n_queens(4)
384 for row in solutions[0]:
385 print(f" {row}")
386
387 # 5. ๊ดํธ ์์ฑ
388 print("\n[5] ๊ดํธ ์์ฑ")
389 n = 3
390 parens = generate_parentheses(n)
391 print(f" {n}์์ ๊ดํธ ({len(parens)}๊ฐ):")
392 print(f" {parens}")
393
394 # 6. ๋จ์ด ๊ฒ์
395 print("\n[6] ๋จ์ด ๊ฒ์ (Word Search)")
396 board = [
397 ['A', 'B', 'C', 'E'],
398 ['S', 'F', 'C', 'S'],
399 ['A', 'D', 'E', 'E']
400 ]
401 print(" ๋ณด๋:")
402 for row in board:
403 print(f" {row}")
404 for word in ["ABCCED", "SEE", "ABCB"]:
405 result = word_search([row[:] for row in board], word)
406 print(f" '{word}' ์กด์ฌ? {result}")
407
408 print("\n" + "=" * 60)
409 print("๋ฐฑํธ๋ํน ํจํด ์ ๋ฆฌ")
410 print("=" * 60)
411 print("""
412 ๋ฐฑํธ๋ํน ํ
ํ๋ฆฟ:
413
414 def backtrack(์ํ):
415 if ์ข
๋ฃ ์กฐ๊ฑด:
416 ๊ฒฐ๊ณผ์ ์ถ๊ฐ
417 return
418
419 for ์ ํ in ์ ํ์ง:
420 if ์ ํจํ์ง ์์ ์ ํ:
421 continue # ๊ฐ์ง์น๊ธฐ (Pruning)
422
423 ์ ํ ์ ์ฉ
424 backtrack(๋ค์ ์ํ)
425 ์ ํ ์ทจ์ # ๋ฐฑํธ๋ํน
426
427 ํต์ฌ ํฌ์ธํธ:
428 1. ์ํ ํํ ๋ฐฉ๋ฒ ๊ฒฐ์
429 2. ์ข
๋ฃ ์กฐ๊ฑด ์ ์
430 3. ๊ฐ์ง์น๊ธฐ๋ก ๋ถํ์ํ ํ์ ์ค์ด๊ธฐ
431 4. ์ํ ๋ณต์ (์๋๋๋ก ๋๋๋ฆฌ๊ธฐ)
432 """)
433
434
435if __name__ == "__main__":
436 main()