💬 문제
🗿 처음 보고
N<=15로 생각보다 작은수이다.
greedy하게 풀 수 있나 계산을 해보자
모든 경우의 수를 계산
퀸 한개를 놓을때마다, N*N 칸을 검증 -> 가능한 칸이 m개 나온다고 가정.
다음 퀸 한개를 놓으려면 m개 케이스(N*N을 통해 도출)*N*N칸을 검증 = O(N^4)
또 다음 퀸 한개를 놓으려면 P개 케이스(N^4를 통해 도출)*N*N칸을 검증 = O(N^6) .....
최종 O(N^N) = O(15^15) = O(4.378938904E17) = O(437,893,890,400,000,000).
제한 시간은 10초 = 1,000,000,000 이므로 시간내에 돌아가지 않는다.
my Daegalee 론 선형적으로밖에 케이스를 제외시키는게 도움이 안된다고 생각해서,, DP인가 ? 라고 생각하기도 하다가 시간을 10초나 준다는걸 생각하니까 일단 최적화를 해야겠다고 생각했다. 역시 my Daegalee로 선형적으로밖에 생각이 안나서 검색 했씁니다.
☕️ 최적화 방법 검색
검색해보니 백트래킹의 정석인 문제라고 하네요
백트래킹
해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.
즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.
답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것
일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.
슬쩍슬쩍 읽으니, 다양한 방법으로 최적화를 시켜나가는 방법이 있습니다.
하나씩 개선해나가는 진기명기show 시작
단순 구현
최적화하지 않은, 그대로의 수도 코드
재귀를 사용한다.
def func(x, y) :
if (y >= n) : # 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution()
return
if(x >= n) :# 가로로 범위를 넘으면, 초기화하고 다음 줄로 넘겨준다.
x = 0
y++
unqueen(x, y) # 체스판에 퀸을 두지 않는다.
func(x+1, y) # 이대로 진행시켜 본다.
queen(x, y) # 체스판에 퀸을 둔다.
if(check_board_error() == true) # 만약 다른 퀸과 간섭하면 이전으로 돌아간다.
return
func(x+1, y) # 이대로 진행시켜 본다.
unqueen(x, y) #이전으로 되돌리기 위해, 뒀던 퀸을 치워준다.
두 가지 경우를 시험해 본다.
1. 이 자리에 퀸을 두지 않고, 다음 칸으로 넘어간다.
2. 이 자리에 퀸을 두고, 다음 칸으로 넘어간다.
단, 이 자리에 퀸을 뒀을때 다른 퀸이 이 퀸을 잡을 수 있다면, 이 동작을 무효로 하고 이전으로 돌아간다.
개선) 같은 행/열에 다수의 퀸이 있을 수 없다
특정 위치에 퀸을 둔 경우, 같은 줄에는 다른 퀸을 두면 안된다.
즉 퀸을 두고, 바로 다음 줄로 점프해 문제가 없다는 뜻이다.
def func( x, y) :
if(y >= n) # 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution()
return
if(x >= n) # 가로로 범위를 넘으면, 초기화하고 다음 줄로 넘겨준다.
x = 0
y+= 1
unqueen(x, y) #체스판에 퀸을 두지 않는다.
func(x+1, y) # 이대로 진행시켜 본다.
queen(x, y) # 체스판에 퀸을 둔다.
if(check_board_error() == True) #만약 다른 퀸과 간섭하면 이전으로 돌아간다.
return
# 위의 if절에 걸리지 않았으니, 퀸을 둘 위치이다.
# 여기에 퀸을 둔다면, 해당 행은 검사하지 않아도 된다.
# 수정전 ) func(x+1, y)
#######################수정부분########################
func(0, y+1) #다음 줄로 개행시키고, x는 맨 앞으로 옮겨준다.
###################################################
unqueen(x, y)
개선) 재귀를 간단히하기
재귀호출 비용도 무시하지 못할 비용이다.
한 줄에 하나만 둘 수 있는데, 함수를 줄 단위로 움직이도록 한다.
즉, 각각의 함수가 줄을 순회하면서 하나의 칸을 선택하고, 그 칸에 퀸을 둔 뒤에 다음 줄로 이동한다는 뜻이다.
def func(int y) :
if(y >= n) # 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution()
return
for x in range (0,n) : # 어느 칸에 둘 지 순회하면서 본다.
if(check_board_error(x, y) == True) # 이 칸에 둘 수 없으면 다음으로 넘긴다.
continue
queen(x, y) #이 칸에 퀸을 둔다.
func(y+1) #다음 줄로 넘어간다.각 줄마다 반복문을 돌리면서 어느 칸에 퀸을 둘지 결정하고,
이미 다른 퀸이 있어서 부딫히는 자리라면 피한다.
그렇지 않다면, 그 자리에 둬보고 다음 줄로 넘긴다.
check_board_error를 간단하게 : 체크용 배열 활용
def check_board_error( x, y) :
for i in range (0, y) # x좌표가 같은 칸 검사
if(board[i][x] == queen) :
return False
for i in range (0, n) :# 우측 아래로 가는 대각선 검사
if(board[y+i][x+i] == queen) :
return False
# 나머지 대각선도 검사...
제일 간단히 생각했을때, 다음과같이 4개의 for문이 있는 O(N) 함수가 나온다.
체크용 배열 check_number 를 활용하여 더 간단하게 만들자!
def func( y) :
if(y >= n) : # 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution()
return
for x in range (0,n) : #어느 칸에 둘 지 순회하면서 본다.
if(check_number[x] == True) : # 이미 같은 x좌표에 퀸이 있으면 다음칸으로
continue
if(check_cross_error(x, y) == True) # 대각선을 검사해서 둘 수 없으면 다음칸으로
continue
queen(x, y) # 이 칸에 퀸을 둔다.
check_number[x] = True # x좌표 배열에 표시해준다.
func(y+1) # 다음 줄로 넘어간다.
check_number[x] = false #바뀐 값을 복원해줌
check_board_error를 간단하게 2 : 대각선 체크
대각선 관계에 있을때의 규칙
우측 위로 가는 대각선은, x,y의 합이 서로 같다. (0,2와 1,1은 같은 대각선에 있다)
우측 아래로 가는 대각선은, x,y의 차가 서로 같다. (1,0과 2,1은 같은 대각선에 있다)
고로, x+y와 x-y가 같다 = 대각선에 놓여져있다
def func( y) :
if(y >= n) : # 세로로 범위를 넘으면, 마지막까지 문제가 없었다는 뜻. 정답으로 추가.
register_solution()
return
for x in range (0, n) : # 어느 칸에 둘 지 순회하면서 본다.
if(check_number[x] == True) continue #가로로 같은칸 검사
if(check_cross_up[x+y] == True) continue # 위로가는 대각선을 검사
if(check_cross_down[x-y+n] == True) continue # 아래로가는 대각선을 검사
queen(x, y) #이 칸에 퀸을 둔다.
check_number[x] = True # x좌표 배열에 표시해준다.
func(y+1) # 다음 줄로 넘어간다.
check_number[x] = False # 바뀐 값을 복원해줌
if(check_cross_down[x-y+n] == True) 부분에서,
다만 x-y는 음수가 될 수 있으니, 배열에 매핑할 경우 보정값이 필요하다.
x-y는 -n보다 작아질 수 없으므로, n을 보정값으로 더해준다.
최종 결과
def solution(y) :
global res_cnt
if(y >= N) : #끝까지 순회한 경우 정답케이스 중 하나이다.
res_cnt += 1
return
for x in range (0, N) :
if (check_x[x] or check_diff[N+x-y] or check_sum[x+y]) : # 놓을 수 있는 자리인지 검증
continue
# 검증을 통과했으니, 체크해둔다
check_diff[N+x-y] = True
check_sum[x+y] = True
check_x[x] = True
solution(y+1) # 다음행 검사
# 재귀에서 돌아왔으니, 다시 uncheck 해둔다
check_diff[N+x-y] = False
check_sum[x+y] = False
check_x[x] = False
check_sum = [False for i in range(300)]
check_diff = [False for i in range(300)]
check_x = [False for i in range(300)]
res_cnt = 0
N = int(input())
solution(0)
print(res_cnt)결과
5초대로 통과했다!!
레퍼런스
단계별 개선 과정이 설명된 블로그 를 보고 정리했습니다.
