출처 :
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
풀이:
n = int(input())
ans = 0
row = [0]* n
def right(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i) :
return False
return True
def queen(x):
global ans # 함수 안에서 ans 값이 변할 수 있도록 해줌
if x == n:
ans += 1
else:
for i in range(n):
row[x] = i #[x,i]에 퀸을 두겠다.
if right(x):
queen(x+1)
queen(0)
print(ans)
전체코드는 위와 같고 하나하나 보려고 한다.
일단 설명하기전 백트래킹을 대할 때는 뒤에서 부터 생각하면서 접근해야한다는 점을 강조하고 싶다.
우선 하나하나 살펴보면
ans : 성공한 경우의 수를 1씩 증가해가기위해 0으로 선언.
row : [0]을 원하는 판의 개수만큼 설정해준다. 그래서 우리가 자주 쓸 기술은 [3,4] 좌표를 row[3]=4 로 표현할 것이다.
1. checking system
def right(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == abs(x - i) :
return False
return True
x는 행의 위치이다. 퀸이 서로 안만나게 하는 방법은 1. 같은 열에 없을 때 2. 같은 행에 없을 때 3. 대각선으로 존재 하지 않을 때다.
1에 대해서는 다음과 같은 row[x] = row[i] 일 땔를 제거 해주면 된다. 예를 들어 row[1] = 2 (1,2) 이고 row[0] = 2 (0,2) 이면 False로 기록할 것이다.
2에 대해서는 우리는 뒤에서 살펴볼 코드에서 한 행에 한번만 입력하게 설정할 것이다. 그래서 자동으로 넘어가자
3에 대해서는 (4,5) 라고 하면 이것에 대각선은 (3,6),(2,7) // (3,4),(2,3) 으로 각 행과 열의 차이를 빼주면 값이 같아야한다.
-> row[x] - row[i] == x - i 이걸 확인하면 될 것이다.
2. queen 두기
def queen(x):
global ans # 함수 안에서 ans 값이 변할 수 있도록 해줌
if x == n:
ans += 1
else:
for i in range(n):
row[x] = i #[x,i]에 퀸을 두겠다.
if right(x):
queen(x+1)
queen(0)
print(ans)
1. global 함수 - 저걸 씀으로서 함수 안에서 ans 값을 변경하고 저장해주는 역할을 해준다. 저걸 쓰지 않으면 ans = 0 으로 출력된다.
2. 행이 7까지 있는데 8까지 성공적으로 도달하면 ans 에 1을 더해준다.
3. 퀸을 어디에 둘 지를 정하는건데 x로 행의 위치를 잡았다면 다음 0~7 까지 열에 값을 넣어줘서 값을 넣은 다음 그 다음 행으로 넘어가서 다시 위치를 두면서 성공했는지 right 함수로 확인하며 진행한다.
아이패드 산김에 자랑 ㅋㅋ ㅎㅎㅎ 빨간색으로진행하고 끝나면 파랑색으로 다시 진행 되면서 ans 가 추가된다고 보면 편한다.
'코딩테스트' 카테고리의 다른 글
백준 9148 신나는 함수 실행 - Python (0) | 2022.02.27 |
---|---|
백준 1003 피보나치 함수 - Python (0) | 2022.02.26 |
백준 14889 스타트와 링크 - Python (0) | 2022.02.12 |
백준 14888 연산자 끼워넣기 - python (0) | 2022.02.05 |
백준 15652 N과 M(4) - python (0) | 2022.02.03 |