[ 백준 / Python ] #9663 N-Queen

2023. 5. 26. 17:13· Koala - 10기/기초 알고리즘 스터디
목차
  1. 문제
  2. Algorithm
  3. Code

문제

 

https://www.acmicpc.net/problem/9663

 

9663번: N-Queen

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

www.acmicpc.net


Algorithm

n*n개의 타일에 퀸 n개를 서로 공격할 수 없게 되는 경우의 수를 출력하는 문제이다. 체스에서 퀸은 상하좌우, 대각선을 전부 이동할 수 있으므로 같은 열에는 둘 수 없다. n개의 열에 n개의 퀸을 두므로, 한 열에는 퀸이 1개만 존재해야한다. 순열을 재귀함수로 구현할때, 배열을 만들어서 선택이 가능한 경우에만 재귀함수를 돌리는 거에서 착안하여 재귀를 돌릴때마다 그 자리에 퀸을 두어도 되는지 안되는지 확인하기 위해 visited라는 배열을 만들고, 그 자리에 두었으면 상하좌우, 대각선에 두면 안되도록 배열의 값을 조정해준다.

n을 입력받고, n*n 크기의 visited배열을 만들어준다. 이때 True,False로 만들지 말고, 초기값을 모두 0으로 만들어준다. 이유는 이따가 봐보자

재귀함수 recur을 선언해주고, cur을 현재 열로 생각하고 변수를 만들어둔다. cur이 n이면 n개의 퀸이 서로 공격할 수 없는 경우이므로 return하고 cnt+=1을 해준다. 이제 cur열에 퀸을 둘건데, 아까 만든 visited배열의 cur열이 0보다 크면 continue로 제외를 시켜준다. cur열 i행에 퀸을 두었다면 cur+1부터 n까지의 i행을 전부 +=1로 해준다. 왜 +=1을 하냐면 True False로 설정해주면 이따가 재귀함수가 cur+1부터 n까지 다 돌고 나와서 cur열 i+1행에 두었을때를 찾아야하는데, 이때 초기화 하는 과정에서 이러한 오류가 나올 수 있다.

visited배열을 True False로 설정했을 때 제일 왼쪽이 cur-1열 까지 퀸을 둔 모습이고, 가운데가 cur열에 퀸을 두고 난 뒤의 visited배열이다. 그 다음에 cur+1부터 n까지 돌고 난 뒤에 초기화를 한 모습이가장 오른쪽에 있는 그림이다. 왼쪽과 오른쪽이 같아야하는데 다른 모습이다. 그래서 int로 초기값을 잡아주고 +1, -1을 해주었다. 

이제 퀸을 기준으로 왼쪽, 오른쪽 대각선 지점의 배열의 값을 +=1을 해주고 재귀함수를 호출해서 recur(cur+1)로 다음열로 넘어간다. 재귀함수가 다 돌고 나오면 초기화를 위해 +1해주었던 지점을 전부 -1해준다.

현재 행을 기준으로 아래쪽 행들의 값만 조정해 주면 가능한 경우만 보게 되도록 설정하고, cur이 n에 도달하면 퀸들이 서로 공격할 수 없으므로 cnt값을 더해주면 된다!

그리고 recur(0)을 해주고, cnt값을 출력해주면 값이 나온다!


 

 

Code

input = __import__('sys').stdin.readline

n = int(input())
visited = [[0 for _ in range(n)]for _ in range(n)]
cnt = 0
def recur(cur):
    global cnt
    if cur == n:
        cnt+=1
        return

    for i in range(n):
        if visited[cur][i] > 0: #현재 cur열에서 행을 보는데 visited값이 0보다 크면 여기에 두면 안되므로 pass
            continue

 #(cur,i)를 선택했으므로 이 지점을 기준으로 아래, 우하향 대각선, 좌하향대각선을 전부 두면 안되도록 설정
        for t in range(n-cur):
            visited[cur+t][i] +=1 # cur ~ n까지 두면 안되도록 설정
        x = 1
        while True: # (cur,i)를 기준으로 좌하향 대각선에 두면 안되도록 설정
            if cur+x > n-1 or i-x <0: 
                break
            visited[cur+x][i-x] += 1
            x+=1

        x = 1
        while True: # (cur,i)를 기준으로 우하향 대각선에 두면 안되도록 설정
            if cur + x > n - 1 or i + x > n-1:
                break
            visited[cur + x][i + x] += 1
            x += 1

        recur(cur+1) # 재귀 호출후 다음 열로 넘어감
        
        # 재귀가 다 돌고 나오면 이전상태로 리셋한다.
        
        for t in range(n - cur):
            visited[cur + t][i] -= 1
        x = 1
        while True:
            if cur + x > n - 1 or i - x < 0:
                break
            visited[cur + x][i - x] -= 1
            x += 1

        x = 1
        while True:
            if cur + x > n - 1 or i + x > n - 1:
                break
            visited[cur + x][i + x] -= 1
            x += 1

recur(0)

print(cnt)

 

저작자표시 (새창열림)

'Koala - 10기 > 기초 알고리즘 스터디' 카테고리의 다른 글

[ 백준 / Python ] #1914 하노이의 탑  (0) 2023.05.27
[ 백준 / Python ] #5430 AC  (0) 2023.05.21
[ 백준 / Python ] #1515 수 이어 쓰기  (0) 2023.05.19
[백준 / Python] # 2812번 크게 만들기  (0) 2023.05.13
[백준 / Python] #1124 언더프라임  (0) 2023.05.12
  1. 문제
  2. Algorithm
  3. Code
'Koala - 10기/기초 알고리즘 스터디' 카테고리의 다른 글
  • [ 백준 / Python ] #1914 하노이의 탑
  • [ 백준 / Python ] #5430 AC
  • [ 백준 / Python ] #1515 수 이어 쓰기
  • [백준 / Python] # 2812번 크게 만들기
KauKoala
KauKoala
항공대 알고리즘 동아리 Koala 🥰
Koala항공대 알고리즘 동아리 Koala 🥰
KauKoala
Koala
KauKoala
전체
오늘
어제
  • 분류 전체보기 (1884)
    • 공지 게시판 (10)
    • 정보 게시판 (8)
    • Codeforce (15)
    • acm-icpc (6)
    • Koala - 1기 (16)
    • Koala - 2기 (111)
      • Programming Contest (1)
      • A반 (20)
      • B반 (39)
      • C반 (22)
      • 기초 강의 (18)
    • Koala - 3기 (10)
      • 기초 스터디 (7)
    • Koala - 4기 (67)
    • Koala - 5기 (144)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (68)
    • Koala - 6기 (102)
      • 기초 알고리즘 스터디 (75)
      • 코딩테스트 준비 스터디 (25)
      • 모의 테스트 스터디 (1)
    • Koala - 7기 (167)
      • 기초 알고리즘 스터디 (97)
      • 코딩테스트 준비 스터디 (68)
      • 모의 테스트 스터디 (1)
    • Koala - 8기 (44)
      • 기초 알고리즘 스터디 (32)
      • 코딩테스트 준비 스터디 (10)
      • 코드포스 버츄얼 스터디 (0)
      • 프로그래머스 LV2 스터디 (0)
    • Koala - 9기 (205)
      • 기초 알고리즘 스터디 (138)
      • 코딩테스트 준비 스터디 (64)
      • 모의테스트 준비 스터디 (1)
    • Koala - 10기 (117)
      • 기초 알고리즘 스터디 (30)
      • 코딩테스트 준비 스터디 (86)
      • 모의테스트 준비 스터디 (1)
    • Koala - 11기 (151)
      • 기초 알고리즘 스터디 (46)
      • 코딩테스트 준비 스터디 (104)
      • 모의테스트 준비 스터디 (1)
    • Koala - 12기 (86)
      • 기초 알고리즘 스터디 (31)
      • 코딩테스트 준비 스터디 (55)
    • Koala - 13기 (119)
      • 기초 알고리즘 스터디 (52)
      • 코딩테스트 준비 스터디 (67)
    • Koala - 14기 (116)
      • 기초 알고리즘 스터디 (39)
      • 코딩테스트 준비 스터디 (77)
    • Koala - 15기 (138)
      • 기초 알고리즘 스터디 (73)
      • 코딩테스트 준비 스터디 (65)
    • Koala - 16기 (47)
      • 코딩테스트 기초 스터디 (16)
      • 코딩테스트 심화 스터디 (31)
    • Koala - 17기 (62)
      • 코딩테스트 기초 스터디 (15)
      • 코딩테스트 심화 스터디 (47)
    • Koala - 18기 (31)
      • 코딩테스트 기초 스터디 (11)
      • 코딩테스트 심화 스터디 (20)
    • Koala - 19기 (38)
      • 코딩테스트 기초 스터디 (7)
      • 코딩테스트 심화 스터디 (31)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

  • 🐨항공대 알고리즘 학회 Koala 3기 모집
  • 🐨항공대 알고리즘 학회 Koala 2기 모집
  • 소모임 소개

인기 글

태그

  • BFS
  • BOJ
  • dp
  • dfs
  • C++
  • 백준
  • 백트래킹
  • 파이썬

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.3.0
KauKoala
[ 백준 / Python ] #9663 N-Queen
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.