๋ฌธ์
https://www.acmicpc.net/problem/9663
๋ฐฑ์ค ๋จ๊ณ๋ณ ํ์ด - ๋ฐฑํธ๋ํน
ํ์ด
๊ธฐ์ค์ด ๋ฐ๋๊ฒ์ธ์ง ์ผ๋ฐ์ ์ธ ์ฝ๋๋ก๋ ํต๊ณผ๋์ง ์์๋ค.
๊ฒฐ๊ตญ ๋นํธ๋ง์คํน์ ์ด์ฉํ ํ์ด๋ก ์ฑ๊ณต...
# 1
def dfs(row, ld, rd, n):
if row == all_bits:
return 1
count = 0
poss = all_bits & ~(row | ld | rd)
while poss:
bit = poss & -poss
poss -= bit
count += dfs(row | bit, (ld | bit) << 1, (rd | bit) >> 1, n)
return count
# 2
N = int(open(0).readline())
all_bits = (1 << N) - 1
print(dfs(0, 0, 0, N))
- row: ํ์ฌ ํ
- ld, rd: ํธ์ ์ผ์ชฝ ๋๊ฐ์ , ์ค๋ฅธ์ชฝ ๋๊ฐ์
- poss: ๊ฐ๋ฅํ ์ด์ ์์น ํ์ (ex: 0110 => ๋๋ฒ์งธ, ์ธ๋ฒ์งธ ์ด ๊ฐ๋ฅ)
- bit: ๊ฐ๋ฅํ ์ด ์ค ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ ์์นํ ์ด ์ ํ(๋ชจ๋ ๊ฐ๋ฅํ ์์น ์์ฐจ์ ์ผ๋ก ์ํ ์์ )
- count: ํ์ฌ ์ํ์์ ์ฐพ์ ํด๋ต์ ์
๋จ๊ณ๋ณ ํ์ด
1. ํจ์ ์์ฑ
def dfs(row, ld, rd, n):
if row == all_bits:
return 1
count = 0
# 1
poss = all_bits & ~(row | ld | rd) # row, ld, rd๊ฐ ์๋ ์ด => ๊ฐ๋ฅํ ์ด
# 2
while poss:
bit = poss & -poss
# 3
poss -= bit
# 4
count += dfs(row | bit, (ld | bit) << 1, (rd | bit) >> 1, n)
return count
poss๋ก ๊ฐ๋ฅํ ์ด์ ์ฒดํฌํ๋ค.(row | ld | rd)๋ ํธ๋ค์ด ์์นํ ํ, ํธ์ ์ผ์ชฝ/์ค๋ฅธ์ชฝ ๋๊ฐ์ ์ ๋ปํ๋ค.
์ด๊ฑธ~๋ฅผ ํตํด ๋ค์ง์ด์ฃผ๋ฉด ๊ฐ๋ฅํ ์ด์ ์์น๊ฐ ๋๋ค.all_bits๋ฅผ ํตํด NxN์ ํฌ๊ธฐ๋ก ํ์ ํ๋ค.
poss๊ฐ ์กด์ฌํ๋ ๋์ ์๋์ ํ์๋ฅผ ๋ฐ๋ณตํ๋ค.poss & -poss: ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ 1์ ์ ํ. (๊ฐ๋ฅํ ์ด์ ์์น ์ค ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ ์ด์ ์ ํ)poss๊ฐ 1001์ด๋ผ ๊ฐ์ ํ๋ฉด,-poss = 0111์ด ๋๋ค.AND์ฐ์ฐ์ผ๋ก0001์ด ๋จ๊ฒ ๋๋ฉฐ, ๊ฐ์ฅ ์ค๋ฅธ์ชฝ์ ์ด์ ๋ปํ๋ค.
- ๊ฐ๋ฅํ ์ด์ ์์น์์ ์ ํํ ์ด์ ์์น(
bit)๋ฅผ ์ ๊ฑฐ. dfs()์ ๋ค์ ์ธ์๋ฅผ ๋ฃ์ด์ฃผ๊ณ , ๊ทธ ๊ฐ์count์ ์ถ๊ฐํ๋ค.row | bit: ํธ๋ค์ ์์น๊ฐrow์ ์์นbit์ถ๊ฐ(ld | bit) << 1:ld์ ํ์ฌ ํธ์ ์์นbit๋ฅผ ์ถ๊ฐํ ๋ค ์ผ์ชฝ์ผ๋ก 1 ์ํํธ.(์ผ์ชฝ์ผ๋ก 1์ด ์ด๋)(rd | bit) >> 1: ์์ ๊ฐ์.
2. ์ฒด์คํ ์ ๋ ฅ๊ฐ ๋ฐ๊ธฐ, ๊ฒฐ๊ณผ ์ถ๋ ฅ
N = int(open(0).readline())
all_bits = (1 << N) - 1
- ๋จผ์ ์ฒด์คํ์ ํฌ๊ธฐ, ํธ์ ๊ฐฏ์
N์ ์ ๋ ฅ๋ฐ๋๋ค. N์ ํฌ๊ธฐ๋งํผ 1๋ก ์ด๋ฃจ์ด์ง ์ด์ง ๋นํธ์ด์ ์์ฑํด์ค๋ค.- ๋ง์ฝ
N = 4์ผ๋,1 << N = 10000์ด ๋๊ณ , ์ฌ๊ธฐ์ 1์ ๋นผ์ค1111๋ก ๋ง๋ค์ด์ค๋ค.
- ๋ง์ฝ
0, 0, N์ ์ธ์๊ฐ์ผ๋ก ํจ์๋ฅผ ์คํ์ํจ ๋ค ๊ฐ์ ์ถ๋ ฅ.