๐ฑ ๋ฐฑํธ๋ํน
๋ฐฑํธ๋ํน(BackTracking)์ ๋ค๋ฅธ ์๊ณ ๋ฆฌ์ฆ ์ ๋๋ ์๋๋ผ ์ผ์ข ์ ๊ธฐ๋ฒ, ์ ๋ต์ ๋๋ค. ๋ฐฑํธ๋ํน(Backtracking, ํด๊ฐ ๊ฒ์)์ ์ผ์ข ์ ํด๋ฅผ ์ฐพ๊ธฐ ์ํด ์ฌ๊ท์ ์ผ๋ก ๋ฌธ์ ๋ฅผ ํ์ด๋๊ฐ๋ค๊ฐ ์ ์ฝ ์กฐ๊ฑด์ ์๋ฐฐ๊ฐ ๋๋ค๋ฉด ์ ์ธ ํ์๋ฅผ ํ๊ณ ๋ค์ ๋จ๊ณ๋ก ๋์ด๊ฐ๋ ๋ฐฉ๋ฒ์ ๋๋ค.
๊ตฌํํ๋ ๋ฐฉ๋ฒ
๊ฒฐ๋ก ์ ์ผ๋ก, ๋ฐฑํธ๋ํน ๊ธฐ๋ฒ์ ์ ์ฝ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ฒฝ์ฐ๋ฅผ ํ์ํ๊ธฐ ๋๋ฌธ์ DFS์ BFS์ ๊ฐ์ ์์ ํ์ ๊ธฐ๋ฒ์ผ๋ก ๊ตฌํ์ด ๊ฐ๋ฅํฉ๋๋ค.
๊ทธ๋ฌ๋, ํน์ฑ์ ์ ์ฝ์กฐ๊ฑด์ ๋ง์กฑํ์ง ์์ผ๋ฉด ๋ค์ ์ด์ ๋ ธ๋๋ก ๋์์์ผ ํ๊ธฐ ๋๋ฌธ์ BFS๋ณด๋ค๋ DFS๋ก ๊ตฌํํ๊ธฐ ํธํฉ๋๋ค.๋ฌผ๋ก ์๊ฐ์ด ๋ถ์กฑํ ๊ฒฝ์ฐ์ BFS๋ก ํ์ด์ผํฉ๋๋ค.
๊ทธ๋ฆฌ๊ณ ๋ง์ฝ ์ ์ฝ์กฐ๊ฑด์ ๋ง์กฑํ์ง ์๋ ๊ฒฝ์ฐ ๋ค๋ฅธ ๋ฃจํธ๋ก ๋์๊ฐ์ผ ํฉ๋๋ค. ์ด๋, ์กฐ๊ฑด์ ๋ง์กฑํ๋์ง ํ์ธํ๋ ๊ฒ์ Promising์ด๋ผํ๊ณ ์กฐ๊ฑด์ ๋ง์กฑํ์ง ์์ ๋ค๋ฅธ ๋ฃจํธ๋ก ๊ฐ๋ ๊ฒ์ ๊ฐ์น์น๊ธฐ(Pruning)์ด๋ผ๊ณ ํฉ๋๋ค.
๋ฐ๋ผ์, DFS๋ฅผ ํตํด ๋ชจ๋ ๋ ธ๋๋ฅผ ํ์ํ๋ฉด์ ์ ์ฝ ์กฐ๊ฑด์ ๋ง์กฑํ์ง ์๋ ๊ฒฝ์ฐ ๊ฐ์ง์น๊ธฐ(Pruning)๋ก ์ ์ธ์ํค๋ฉด ๋ฉ๋๋ค.
๋ฐฑ ํธ๋ํน ๋ฌธ์ ํ์ด(N-Queen)
๋ค์ N-Queen ๋ฌธ์ ๋ฅผ ๋ด ์๋ค.
NXN ํฌ๊ธฐ์ ์ฒด์ค ๋ณด๋ ์์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๋ฌธ์ ์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋ ํธ์ ๋๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ ๋ ฅ : ์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค. (1 <= N < 15) ex) `8`
- ์ถ๋ ฅ : ์ฒซ์งธ ์ค์ ํธ N๊ฐ๋ฅผ ์๋ก ๊ณต๊ฒฉํ ์ ์๊ฒ ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ค. ex) `92`
์ฌ๊ธฐ์ Queen์ ๋์ง ๋ชปํ๋ ๊ฒฝ์ฐ๋ ๋๊ฐ์ ์ ๊ฒฝ์ฐ์ ๋ฐ๋ก ์์ ํธ์ด ์๋ ๊ฒฝ์ฐ์ ๋๋ค.
๋จผ์ , ์ด๋ฒ ๋ฌธ์ ์์๋ ๊ตณ์ด ์ด์ฐจ์ ๋ฐฐ์ด๊น์ง ๋ง๋ค ํ์๊ฐ ์์ต๋๋ค. ํด๋น ํ(Row)์ ํธ์ ๋์ ์ ์๋์ง๋ฅผ ํ๋ณํ๋ฉด ๋๊ธฐ ๋๋ฌธ์ ๋๋ค.
์ ์ฝ์กฐ๊ฑด์ธ ๋๊ฐ์ ๊ณผ ๋ฐ๋ก ์์ ์์ง ์์ผ๋ฉด ๋ค์ ํ(row)์ผ๋ก ๋์ด๊ฐ๋ ๋๊ณ ์์ผ๋ฉด ๋ค์ ์ด๋ก ํ์ํ๋ ์ฝ๋๋ฅผ ์์ฑํ๋ฉด ๋ฉ๋๋ค.
๋ค์ ๊ทธ๋ฆผ ์ฒ๋ผ, ํธ์ ์ฒซ๋ฒ์งธ ํ์ ์ฒซ๋ฒ์งธ ์ด์ ๋๋ค๊ณ ๊ฐ์ ํด๋ด ์๋ค. ์ฒซ๋ฒ์งธ ์ด์ ๊ทธ๋ฅ ๋ ์ ์์ต๋๋ค.
๋ค์ ํ์ ๊ฒฝ์ฐ๋ ์ด๋จ๊น์?
๋ค์ ํ์ ๊ฒฝ์ฐ ๊ฐ์ ํ์ ํธ์ ๋๋ค๊ณ ๊ฐ์ ํ๋ฉด ๋ฐ๋ก ์์ ํธ์ด ์๊ธฐ ๋๋ฌธ์ ๋์ ์ ์์ ๊ฒ์ ๋๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๋ค์ ์ด์ ๋์ด์ผ ๊ฐ๋ฅํฉ๋๋ค.
์ด๋ฐ์์ผ๋ก ์์ฑํ๋ค๋ณด๋ฉด ์ธ์ ๊ฐ X๊ฐ N๊น์ง ๋์ฐฉํ๊ฒ ๋ฉ๋๋ค. ์ด๋ด ๋ ๊ฒฝ์ฐ์ ์๊ฐ ํ๋ ์ถ๊ฐ๋ฉ๋๋ค.
๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ์๋ ๋ค์ ์ฌ๊ท์ ์ผ๋ก ์งํํ๊ฒ ๋ฉ๋๋ค.
def check(x):
"""
x๋ฒ์งธ ํ์ QUEEN์ ๋์ด๋ ๊ด์ฐฎ์์ง ํ์ธ
"""
# ๊ฐ ์ด์ ํ๋ค(i)๊ณผ ํ์ฌํ(x) ํ๋์ฉ ํ์ธ
for i in range(x):
# ์์ชฝ ํ์ ๋ค๋ฅธ ํธ์ด ๋์ฌ ์์ผ๋ฉด False ๋ฐํ
if row[x] == row[i]:
return False
# ๋๊ฐ์ ๋ฐฉํฅ ๊ฒน์น๋๊ฒ ์๋ค๋ฉด False ๋ฐํ
if abs(row[x] - row[i]) == x - i:
return False
return True
def dfs(x):
"""
`x`๋ฒ์งธ ํ์ ๋ํด ์ฒ๋ฆฌ (์ฒซ๋ฒ์จฐ ํ ๋ถํฐ)
- n๋ฒ์งธ ํ ๊น์ง ๋ชจ๋ ํธ์ ๋์ ์ ์๋ ๊ฒฝ์ฐ์ `result += 1`
- ๋ชจ๋ ํ์ ๋ํด ๊ณ์ฐ
- x ๋ฒ์งธ์ ํ์ ๊ฐ ์ด(0 ~ N-1)์ ํธ์ ๋๋ค๊ณ ๊ฐ์ ํ๋ค.
- ํด๋น ์์น์ Queen์ ๋์ด๋ ๊ด์ฐฎ์ผ๋ฉด ๋ค์ ํ์ผ๋ก ๋์๊ฐ๋ค.
"""
global result
if x == n:
result += 1
else:
for i in range(n):
# ์ฐ์ , Queen์ ๋์๋ค๊ณ ๊ฐ์
row[x] = i
# ํด๋น ์์น์ ํธ์ ๋์ด๋ ๊ด์ฐฎ์์ง `check(x)`
if check(x):
dfs(x + 1) # ๋์ ์ ์๋ค๋ฉด ๋ค์ํ์ผ๋ก
n = int(input())
row = [0] * n # ํ์ ๋ํ ์ ๋ณด
result = 0
dfs(0)
print(result)
๐ ์ํธ๋ง๋ค๊ธฐ ๋ฌธ์
[๋ฐฑ์ค1759] - ์ํธ๋ง๋ค๊ธฐโ
ํด๋น ๋ฌธ์ ๋ ๋ช๊ฐ์ง ์กฐ๊ฑด์ ํด๋นํ๋ ์ํธ๋ค์ ๋ง๋๋ ๋ฌธ์ ์ ๋๋ค.
- ๋ ๊ฐ ์ด์์ ์์๊ณผ ํ๊ฐ ์ด์์ ๋ชจ์์ผ๋ก ์ด๋ฃจ์ด์ง๋ค.
- ๋ฌธ์๊ฐ ์ฌ์ ์ ์์๋๋ก ๋ง๋ค์ด์ ธ ์์ด์ผ ํ๋ค.
- ์ค๋ณต์ ํ์ฉํ์ง ์๋๋ค.
๋จผ์ , 4๊ธ์์ ์ํธ๋ฅผ ๋ง๋ค๋ ค๋ฉด ๋ฌธ์์ด์ ์ ๋ ฌํด์ผํฉ๋๋ค. ์ด์ ๋ ์ฌ์ ์ ์์๋๋ก ๋ง๋ค์ด์ผ ํ๊ธฐ ๋๋ฌธ์ ๋๋ค.
๊ทธ๋ฆฌ๊ณ 1๊ฐ ์ด์์ ์์์ด ํฌํจ๋์ด์ผ ํ๋ค๊ณ ํ๊ธฐ ๋๋ฌธ์ `vowels`๋ผ๋ ์์ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค์ด ์ค๋๋ค.
vowels = ['a', 'e', 'i', 'o', 'u'] # ์ต์ ํ๊ฐ์ ๋ชจ์
l, c = map(int, input().split(" "))
words = [i for i in input().split(" ")]
words.sort()
์ค์ ๋ก ๋ฐฐ์ด์ ๋ฌธ์๋ฅผ ๋ฃ๊ณ ์ ๋ฌธ์๊ฐ ํ์ฌ ๋ฌธ์๋ณด๋ค ์์ ๊ฒฝ์ฐ์๋ง ์ํธ๋ฅผ ๋ง๋ค ์ ์๋๋ก ์ฝ๋๋ฅผ ์์ฑํด์ผ ํฉ๋๋ค.
์ฒซ๋ฌธ์๋ ์ฌ์ ์ ์์๋ก ๊ฐ์ฅ ์์ ์๋ ๋ฌธ์ 3๊ฐ๋ง ๊ฐ๋ฅํฉ๋๋ค. ๋ง์ฝ `t`๊ฐ ๊ฐ์ฅ ์์ ๋์ค๋ฉด `tw`๋ค์์ผ๋ก ๋ง๋ค ์ ์๋ ๋ฌธ์๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋๋ค.
result = []
for i in range(c - l + 1):
a = [words[i]]
bt(a) # [a] , [c], [i]
์ด๋ฒ์ ๋ฐฑํธ๋ํน์ ๊ตฌํํ๋ ค๊ณ ํฉ๋๋ค.
๋ง์ฝ ๋ฌธ์์ด์ด 4๊ฐ์ธ ์ํธ๊ฐ ๋ค ์ฑ์์ก์ ๊ฒฝ์ฐ์ ํด๋น ๋ฌธ์์ด(`result`)์ ์ถ๋ ฅํ๊ณ ๊ทธ ์ ๊น์ง๋ ๋ฌธ์๋ฅผ ์๋ก ๋น๊ตํ๋ฉด์ ์ฑ์ธ ์์ ์ ๋๋ค.
def bt(result):
if len(result) == l:
if check(result):
print("".join(result))
return
for i in range(len(result), c):
if result[-1] < words[i]:
result.append(words[i])
bt(result)
result.pop()
๊ทธ ๋ค์, `check` ํจ์๋ฅผ ํตํด ๋ฌธ์์ด์ ๋ชจ์์ด 1๊ฐ์ด์์ธ์ง ์์์ด 2๊ฐ์ด์์ธ์ง๋ฅผ ํ์ธํด์ผํฉ๋๋ค.
๋ง์ฝ ์ํธ์ `a`๋ `i`๊ฐ ๋ค์ด๊ฐ ์์ง ์์ผ๋ฉด ๋ค์ ๋์๊ฐ ๋ค์ ๋ฌธ์๋ก ํ์ธํ๊ฒ ๋๋ ๊ตฌ์กฐ์ ๋๋ค.
def check(result):
v, c = 0, 0
for i in result:
if i in vowels:
v += 1
else:
c += 1
if v >= 1 and c >= 2:
return True
else:
return False
โ๏ธ ๋ง์น๋ฉฐ
์ค๋๋ ์ ์ ํฌ์คํธ๋ฅผ ์ฝ์ด์ฃผ์ ์ ๊ฐ์ฌํฉ๋๋ค.
์ค๋ช ์ด ๋ถ์กฑํ๊ฑฐ๋ ์ดํดํ๊ธฐ ์ด๋ ต๊ฑฐ๋ ์๋ชป๋ ๋ถ๋ถ์ด ์์ผ๋ฉด ๋ถ๋ด์์ด ๋๊ธ๋ก ๋จ๊ฒจ์ฃผ์๋ฉด ๊ฐ์ฌํ๊ฒ ์ต๋๋ค.
'Algorithm Study' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ์ฆ(๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ) (0) | 2024.04.19 |
---|---|
DFS, BFS ๊ทธ๋ํ ํ์ ์๊ณ ๋ฆฌ์ฆ 1 (0) | 2024.03.21 |
ํธ๋ฆฌ ์ํ ์๊ณ ๋ฆฌ์ฆ (0) | 2024.03.14 |
[์ฝํ ์คํฐ๋] ์ ๋ ฌ (0) | 2024.03.11 |
์ฐ์ ์์ ํ์ ํ์ ์ฐจ์ด๋ฅผ ์์๋ณด์. (0) | 2024.02.24 |