9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
재귀알고리즘의 대표 문제 중 하나인 퀸 문제다. 외판원 순환2랑 비슷하지만, 경우의 수가 더 많고 공간적으로 생각할 것이 더 많은 문제이다.
- 대전략 :
N * N 으로 체스판을 만들고, T/F로 구분한다. (퀸을 배치했거나 갈 수 없는 곳은 F)
우선 y=0인 곳에 퀸을 놓는다. 그 후, 다음 y열~N-1열에서 같은 x방향, 대각선을 모두 False한다.
그리고 다음 y열에서 x=0행부터 N-1행까지 True를 탐색하고, True자리에 퀸을 놓는다.
일단 체스판을 만들자
N = int(sys.stdin.readline())
n = N
plate = [[0 for col in range(N)] for row in range(N)]
count = 0count는 성공할 때마다 +1 씩 될 것이다.
그리고 여왕님을 배치할 함수도 만들어주자. 필요 인자는 x,y좌표와 퀸의 갯수이다.
(생각해보니 x 가 필요한가? 어차피 y가 올라갈 때 마다 0부터 시작할건데)
성공 조건은 (N-1,N-1)에 도달했을 때, n(남아있는 여왕 갯수)가 0이면 성공. 아니면 실패
if x == N-1 and i == N-1:
# 성공
if n == 0:
count += 1
return
# 실패
else:
return
그리고 퀸을 배치했으므로 퀸이랑 겹치는 동선을 False해준다. 그리고 다음 재귀함수를 실행하고, False를 복원시켜주자
# True일 때, 여왕 배치
elif not plate[x][i]:
plate[x][i] = 2
dx = [-1, 0, 1]
dy = [-1, 0, 1]
#x줄 제거
nx = x
ny = y
while ny < N:
ny = y + dy[2]
plate[x][ny] = False
# 대각선 정방향 제거
nx = x
ny = y
while nx < N or ny < N:
nx = x + dx[2]
ny = y + dy[2]
plate[nx][ny] = False
# 대각선 역방향 제거
nx = x
ny = y
while nx > -1 or ny < N:
nx = x + dx[0]
ny = y + dy[2]
plate[nx][ny] = False
# 다음 퀸 배치
queen(n-1, y+1)
# 초기화
# x줄 복원
nx = x
ny = y
while ny < N:
ny = y + dy[2]
plate[x][ny] = True
# 대각선 정방향 복원
nx = x
ny = y
while nx < N or ny < N:
nx = x + dx[2]
ny = y + dy[2]
plate[nx][ny] = True
# 대각선 역방향 복원
nx = x
ny = y
while nx > -1 or ny < N:
nx = x + dx[0]
ny = y + dy[2]
plate[nx][ny] = True
코드가 아름답진 않지만 여기가 내 한계이다. 미래의 내가 고쳐주겠지
맨 처음 for가 바뀔때마다 체스판을 초기화시켜주는 함수를 구현했다.
def initializing(N):
for i in range(0,N):
for j in range(0,N):
plate[i][j] = True
j += 1
i += 1
return
그리고 결과창을 보여주는 함수도 짜봤다.
def result():
print("--------------------------------------")
for i in range(N):
for j in range(N):
if plate[i][j] == True:
print("■", end=' ')
elif plate[i][j] == False:
print("□", end=' ')
else:
print("★", end=' ')
j += 1
print()
i += 1
print("--------------------------------------")
return
그리고 전체 코드는 다음과 같다.
import sys
sys.setrecursionlimit(100000)
N = int(sys.stdin.readline())
n = N
plate = [[0 for col in range(N)] for row in range(N)]
count = 0
x = 0
def initializing(N):
for i in range(0,N):
for j in range(0,N):
plate[i][j] = True
j += 1
i += 1
return
def queen(n, y):
global count
global N
global x
for i in range(N): # x좌표
print("x:", i, "y:", y)
# 마지막까지 도달했을 때,
if y == N:
# 성공
if n == 0:
count += 1
print("성공")
return
# 실패
else:
return
# True일 때, 여왕 배치
elif plate[i][y]:
plate[i][y] = False
#x줄 제거
nx = i
ny = y
dx = 1
dy = 1
while ny < N-1:
ny = y + dy
plate[i][ny] = False
dy += 1
# 대각선 정방향 제거
nx = i
ny = y
dx = 1
dy = 1
while nx < N-1 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny] = False
dx += 1
dy += 1
# 대각선 역방향 제거
nx = i
ny = y
dx = -1
dy = 1
while nx > 0 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny] = False
dx -= 1
dy += 1
result()
# 다음 퀸 배치
queen(n-1, y+1)
# 초기화
#x줄 복원
nx = i
ny = y
dx = 1
dy = 1
while ny < N-1:
ny = y + dy
plate[i][ny] = True
dy += 1
# 대각선 정방향 복원
nx = i
ny = y
dx = 1
dy = 1
while nx < N-1 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny] = True
dx += 1
dy += 1
# 대각선 역방향 제거
nx = i
ny = y
dx = -1
dy = 1
while nx > 0 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny] = True
dx -= 1
dy += 1
def result():
print("--------------------------------------")
for i in range(N):
for j in range(N):
if plate[i][j] == True:
print("■", end=' ')
elif plate[i][j] == False:
print("□", end=' ')
else:
print("★", end=' ')
j += 1
print()
i += 1
print("--------------------------------------")
return
for i in range(N):
initializing(N)
queen(N,i)
print(count)
하지만 여기서 문제가 발생했다.
x:3, y:1 다음이 보이는가?
재귀함수가 리턴해서 F처리 했던 곳을 T로 바꾸는 과정에서 다른 퀸의 경로가 걸침에도 불구하고 T를 처리한다.
어지러워진다. 대각선을 처리하면 안되는 것일까. 외판원 문제랑 뭐가 다른 것일까.
현재 생각나는 것은 x, y 좌표를 리스트로 만들어 주는 것이다.
만약 5x5에서 (0,0) 에 퀸을 놓았다면, 퀸 경로 상의 좌표에 [5] (n=5퀸의 경로에 있다는 뜻) 을 넣어준다.
또한, 다음에 놓는 퀸의 경로에 4를 넣어준다. 만약 겹치면 [5,4]이런 식으로 될 것이다.
그러면 복구하는 과정에서 지워도 해당 좌표는 여전히 다른 숫자가 남아있어서 괜찮을 것이다.
이것이 속도를 더 잡아먹지 않을까? 그럴 가능성이 크지만 일단 구현해보겠다.
import sys
sys.setrecursionlimit(100000)
# a = int(sys.stdin.readline())
# a,b = map(int,input().split())
# a = [int(x) for x in input().strip().split()]
#route = list(list(map(int,read().split())) for _ in range())
#read = sys.stdin.readline
N = int(sys.stdin.readline())
n = N
plate = [[0 for col in range(N)] for row in range(N)]
count = 0
x = 0
def initializing(N):
for i in range(0,N):
for j in range(0,N):
plate[i][j] = []
j += 1
i += 1
return
def queen(n, y):
global count
global N
global x
for i in range(N): # x좌표
#print("x:", i, "y:", y, "n:", n)
# 마지막까지 도달했을 때,
if y == N:
# 성공
if n == 0:
count += 1
#print("성공")
return
# 실패
else:
return
# True일 때, 여왕 배치
elif len(plate[i][y]) == 0:
k = i
l = y
plate[k][l].append(0)
#x줄 제거
nx = i
ny = y
dx = 1
dy = 1
while ny < N-1:
ny = y + dy
plate[i][ny].append(n)
dy += 1
# 대각선 정방향 제거
nx = i
ny = y
dx = 1
dy = 1
while nx < N-1 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].append(n)
dx += 1
dy += 1
# 대각선 역방향 제거
nx = i
ny = y
dx = -1
dy = 1
while nx > 0 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].append(n)
dx -= 1
dy += 1
#result()
# 다음 퀸 배치
queen(n-1, y+1)
# 초기화
#x줄 복원
nx = i
ny = y
dx = 1
dy = 1
while ny < N-1:
ny = y + dy
plate[i][ny].remove(n)
dy += 1
# 대각선 정방향 복원
nx = i
ny = y
dx = 1
dy = 1
while nx < N-1 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].remove(n)
dx += 1
dy += 1
# 대각선 역방향 제거
nx = i
ny = y
dx = -1
dy = 1
while nx > 0 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].remove(n)
dx -= 1
dy += 1
plate[k][l].remove(0)
def result():
print("--------------------------------------")
for i in range(N):
for j in range(N):
if 0 in plate[i][j]:
print("★", end=' ')
elif len(plate[i][j]) == 0:
print("■", end=' ')
else:
print("□", end=' ')
j += 1
print()
i += 1
print("--------------------------------------")
return
for i in range(N):
initializing(N)
queen(N,i)
print(count)
구현은 성공했으나, 역시 시간초과가 뜬다.
그런데 결과를 보는 중 뭔가 이상한 것을 발견했다.
첫 퀸을 y=0에서만 돌려야 하는데 다음 열로 넘어가버린 것이다.
분명 처음 queen 함수는 i~N까지만 돌리도록 되어있다.
그러고보니 queen 함수에는 y == N일 때만, 성공 실패 판정을 한다.
즉, x=0, y=N에서 끝나는 것이 아니라 n을 1 줄이고, 다음 x로 넘어가도록 되어있는 것이다.
이 얼마나 큰 자원의 낭비인가!
queen 배치 하기 전에 조건을 하나 더 추가했다.
# 마지막까지 도달했을 때,
if y == N:
# 성공
if n == 0:
count += 1
#print("성공")
return
# 실패
else:
return
# 첫줄에서 실패
elif y >= 1 and n == N:
return
전체 코드는 다음과 같다.
import sys
sys.stdin = open("textfile1.txt","rt")
sys.setrecursionlimit(100000)
#read = sys.stdin.readline
N = int(sys.stdin.readline())
n = N
plate = [[0 for col in range(N)] for row in range(N)]
count = 0
x = 0
def initializing(N):
for i in range(0,N):
for j in range(0,N):
plate[i][j] = []
j += 1
i += 1
return
def queen(n, y):
global count
global N
global x
for i in range(N): # x좌표
#print("x:", i, "y:", y, "n:", n)
# 마지막까지 도달했을 때,
if y == N:
# 성공
if n == 0:
count += 1
#print("성공")
return
# 실패
else:
return
# 첫줄에서 실패
elif y >= 1 and n == N:
return
# True일 때, 여왕 배치
elif len(plate[i][y]) == 0:
k = i
l = y
plate[k][l].append(0)
#x줄 제거
nx = i
ny = y
dx = 1
dy = 1
while ny < N-1:
ny = y + dy
plate[i][ny].append(n)
dy += 1
# 대각선 정방향 제거
nx = i
ny = y
dx = 1
dy = 1
while nx < N-1 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].append(n)
dx += 1
dy += 1
# 대각선 역방향 제거
nx = i
ny = y
dx = -1
dy = 1
while nx > 0 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].append(n)
dx -= 1
dy += 1
result()
# 다음 퀸 배치
queen(n-1, y+1)
# 초기화
#x줄 복원
nx = i
ny = y
dx = 1
dy = 1
while ny < N-1:
ny = y + dy
plate[i][ny].remove(n)
dy += 1
# 대각선 정방향 복원
nx = i
ny = y
dx = 1
dy = 1
while nx < N-1 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].remove(n)
dx += 1
dy += 1
# 대각선 역방향 제거
nx = i
ny = y
dx = -1
dy = 1
while nx > 0 and ny < N-1:
nx = i + dx
ny = y + dy
plate[nx][ny].remove(n)
dx -= 1
dy += 1
plate[k][l].remove(0)
def result():
print("--------------------------------------")
for i in range(N):
for j in range(N):
if 0 in plate[i][j]:
print("★", end=' ')
elif len(plate[i][j]) == 0:
print("■", end=' ')
else:
print("□", end=' ')
j += 1
print()
i += 1
print("--------------------------------------")
return
for i in range(N):
initializing(N)
queen(N,i)
print(count)
제출 결과, 파이썬에서는 시간초과가 떴지만, PyPy에서는 19000ms로 통과했다.
코드도 로직도 깔끔하진 않지만 일단은 통과했다는 것에 의의를 두자.
차후에 파이썬으로도 할 수 있도록 다시 시도해봐야겠다.
'프로그래밍 공부 > 백뚠' 카테고리의 다른 글
| 야구는 9회말 2아웃부터 (백준2053:숫자야구) (0) | 2020.12.17 |
|---|---|
| 아래로부터의 혁명 (백준 9095 : 1, 2, 3 더하기) (0) | 2020.12.17 |
| 이 세상의 모든 세일즈맨을 위하여 (백준 10971번 : 외판원 순회2) (0) | 2020.12.15 |
| 날씨의 아이 (백준 2468번 : 안전 영역) (0) | 2020.12.15 |
| 직사각형에서 탈출 (0) | 2020.12.11 |
댓글