[๋ฐฑ์ค€/pypy3] 9663๋ฒˆ : N-Queen

2021. 4. 12. 02:31

๋ฌธ์ œ

N-Queen ๋ฌธ์ œ๋Š” ํฌ๊ธฐ๊ฐ€ N × N์ธ ์ฒด์ŠคํŒ ์œ„์— ํ€ธ N๊ฐœ๋ฅผ ์„œ๋กœ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๊ฒŒ ๋†“๋Š” ๋ฌธ์ œ์ด๋‹ค.

N์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ€ธ์„ ๋†“๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N < 15)

 

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ํ€ธ N๊ฐœ๋ฅผ ์„œ๋กœ ๊ณต๊ฒฉํ•  ์ˆ˜ ์—†๊ฒŒ ๋†“๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 

์ •๋‹ต

N = int(input())
count = 0

# row : ํ–‰ / right : ์šฐ์ƒํ–ฅ ๋Œ€๊ฐ์„  / left : ์ขŒ์ƒํ–ฅ ๋Œ€๊ฐ์„ 
row, right, left = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)

def solve(j):
    global count
    # N๊ฐœ์˜ ํ€ธ์„ ๋‹ค ๋†“์•˜์„ ๋•Œ
    if j == N:
        count += 1
        return

    for i in range(N):
        # ๋ชจ๋“  ๋ฐฉํ–ฅ์ด False์ผ ๋•Œ = ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ์„ ๋•Œ
        if not (row[i] or right[j + i] or left[N - 1 + j - i]):
            row[i] = right[j+i] = left[N-1+j-i] = True
            solve(j+1)
            row[i] = right[j+i] = left[N-1+j-i] = False


solve(0)
print(count)

์ด ๋ฌธ์ œ๋Š” ํŒŒ์ด์ฌ์„ ํ†ตํ•ด ํ’€ ๊ฒฝ์šฐ ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•˜๊ธฐ ๋•Œ๋ฌธ์— pypy3๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ’€ ์ˆ˜ ์žˆ๋‹ค.

# row : ํ–‰ / right : ์šฐ์ƒํ–ฅ ๋Œ€๊ฐ์„  / left : ์ขŒ์ƒํ–ฅ ๋Œ€๊ฐ์„ 
row, right, left = [False] * N, [False] * (2 * N - 1), [False] * (2 * N - 1)

์ขŒํ‘œ์˜ ๋‘ ์ธ๋ฑ์Šค์˜ ํ•ฉ ๋˜๋Š” ์ฐจ๊ฐ€ ๋‹ค๋ฅธ ์ขŒํ‘œ์˜ ํ•ฉ ๋˜๋Š” ์ฐจ๊ฐ€ ๊ฐ™๋‹ค๋ฉด ๊ฐ™์€ ๋Œ€๊ฐ์„  ์ƒ์— ์กด์žฌํ•จ์„ ์ด์šฉํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด (0,2), (1,1), (2,0)์˜ ๋‘ ์ธ๋ฑ์Šค์˜ ํ•ฉ์€ 2๋กœ ๋ชจ๋‘ ๊ฐ™์œผ๋ฏ€๋กœ ๊ฐ™์€ ์šฐ์ƒํ–ฅ ๋Œ€๊ฐ์„  ์ƒ์— ์œ„์น˜ํ•œ๋‹ค.

๋Œ€๊ฐ์„ ์„ ๋‚˜ํƒ€๋‚ด๋Š” right์™€ left๋Š” ๋‘ ์ธ๋ฑ์Šค์˜ ํ•ฉ๊ณผ ์ฐจ๋กœ ์ด๋ฃจ์–ด์ง€๋ฏ€๋กœ 2*N-1๊ฐœ์˜ ์ธ๋ฑ์Šค๊ฐ€ ํ•„์š”ํ•˜๋‹ค.

 

def solve(j):
    global count
    # N๊ฐœ์˜ ํ€ธ์„ ๋‹ค ๋†“์•˜์„ ๋•Œ
    if j == N:
        count += 1
        return

solve ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค๊ณ  ํ–‰์„ ์˜๋ฏธํ•  j๋ฅผ ์ธ์ž๋กœ ์‚ฌ์šฉํ•˜์—ฌ ๋ชจ๋“  ํ–‰์— ํ€ธ์„ ๋†“์„ ๊ฒƒ์ด๋‹ค.

j๊ฐ€ N๊ณผ ๊ฐ™๋‹ค๋ฉด ๋†“์•„์•ผ ํ•˜๋Š” ๊ฐœ์ˆ˜์˜ ํ€ธ์„ ๊ฐ ํ–‰๋งˆ๋‹ค ๋‹ค ๋†“์•˜๋‹ค๋Š” ๋œป์ด๊ธฐ ๋•Œ๋ฌธ์—

ํ€ธ์„ ๋†“๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ์˜๋ฏธํ•˜๋Š” count์— 1์„ ๋”ํ•ด์ฃผ๊ณ  return ํ•œ๋‹ค.

 

for i in range(N):
        # ๋ชจ๋“  ๋ฐฉํ–ฅ์ด False์ผ ๋•Œ = ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ์„ ๋•Œ
        if not (row[i] or right[j + i] or left[N - 1 + j - i]):
            row[i] = right[j+i] = left[N-1+j-i] = True
            solve(j+1)
            row[i] = right[j+i] = left[N-1+j-i] = False

์ด์ œ ๋งจ ์œ„ ํ–‰๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ์ˆœ์„œ๋Œ€๋กœ ๋‚ด๋ ค๊ฐ€๋ฉด์„œ ๋ชจ๋“  ์—ด์— ํ€ธ์„ ๋†“๋Š”๋‹ค.

๋ชจ๋“  ์—ด i์— ๋Œ€ํ•˜์—ฌ ๋‹ค์Œ ๋ฐ˜๋ณต๋ฌธ์„ ์‹คํ–‰ํ•œ๋‹ค.

ํ•ด๋‹น ์—ด์˜ ํ–‰, ๋Œ€๊ฐ์„ ์ด ๋ชจ๋‘ False๋ผ๋ฉด ํ€ธ์„ ๋†“์„ ์ˆ˜ ์žˆ๋‹ค๋Š” ๋œป์ด๋ฏ€๋กœ

ํ•ด๋‹น ์—ด์˜ ํ–‰, ๋Œ€๊ฐ์„ ์„ True๋กœ ๋ฐ”๊ฟ”์ฃผ๊ณ  ๋‹ค์Œ ํ–‰์ธ solve(j+1)์„ ํ˜ธ์ถœํ•œ๋‹ค.

๋‹ค์Œ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์„ธ๊ธฐ ์œ„ํ•ด ํ–‰๊ณผ ๋Œ€๊ฐ์„ ์„ ์˜๋ฏธํ•˜๋Š” row, right, left๋ฅผ ๋‹ค์‹œ Flase๋กœ ์ดˆ๊ธฐํ™”ํ•œ๋‹ค.

 

์•„๋ž˜ ์ฃผ์†Œ์˜ ์„ค๋ช…์„ ์ฐธ๊ณ ํ•˜์˜€๋‹ค.

rebas.kr/761

728x90

BELATED ARTICLES

more