N-Queen 문제는 백트랙킹의 대표적인 문제이다.
- 체스의 Queen은 같은 행, 열, 대각선에 대해서 공격할 수 있다.
- NxN 체스판에서 서로 공격하지 않는 Queen을 몇 개 둘 수 있나? 가 문제이다.
문제는 간단하지만, 풀이과정은 간단하지 않다.
처음에는 SWEA에서도 풀이한 문제이기 때문에, 이틀 전에 교수님께서 짜신 코드를 생각하면서 다음과 같이 제출했다.
# n-queen
def queen(row, k):
global cnt
if row == k:
cnt += 1
return
else:
for j in range(N):
can_position = True
# 열 검사
for l in range(0, row+1):
if board[l][j] == 1:
can_position = False
# 대각선 1 검사
for l in range(0, row+1):
if 0 <= j-l < N and board[row-l][j-l] == 1:
can_position = False
# 대각선 2 검사
for l in range(0, row+1):
if 0 <= j+l < N and board[row-l][j+l] == 1:
can_position = False
if can_position == True:
board[row][j] = 1
queen(row+1, k)
board[row][j] = 0
N = int(input())
board = [[0]*N for _ in range(N)]
cnt = 0
queen(0, N)
print(cnt)
처음에는 board라는 NxN 짜리 판을 만들어서, 직접 queen을 하나씩 두면서 새로운 자리에 대해서 board의 위치마다 다 탐색을 했다.
N ≤ 10 까지는 나름 빠르게 수행했으나, 그 이상으로 커질 수록 검사해야 할 가짓수가 기하급수적으로 늘어나면서
시간초과
가 발생했다. 게시판을 보니, 파이썬으로 제출 할 경우 특히 시간초과가 많이 발생한 것 같았다.
따라서 코드를 처음부터 수정하기로 결심했다.
💡
어떻게 하면 경우의 수를 줄일 수 있을까?
- 일단 처음 이 문제를 본 내 아이디어 대로 진행해 보기로 했다!
- possible 이라는 함수를 만들어 보기로 했다.
- 열검사를 줄이기 위해 visited를 사용했다.
- 대각선 검사를 위해서 i + j의 합과 차를 사용했다. 중간에 return하게 만들어서 시간복잡도를 줄여보았다.
def queen(row, n): # row는 행, n은 주어진 N
global cnt
if row == n: # N까지 행을 다 찾았으면 카운트를 1 증가시킨다.
cnt += 1
for i in range(N):
if visited[i] == 0: # 해당 열에 방문하지 않았고
if possible(row, i): # 주어진 행에 대해서 열에 둘 수 있을 때
visited[i] = 1 # 방문처리
queen_list.append((row,i)) # queen리스트에 추가하기
queen(row+1, n) # 다음 행으로 가서 queen 찾기
queen_list.remove((row, i)) # 이하는 원복 과정
visited[i] = 0
def possible(i,j):
# 이미 열은 visited를 통해서 걸러내고 있으므로, 대각선에 대해서만 검사하면 된다.
if not queen_list: # 아무원소도 없을 경우에는 True를 반환한다.
return True
for qi, qj in queen_list: # queen_list 안에 있는 모든 queen들에 대해서 검사해야 한다.
if i + j == qi + qj:
return False
if j - i == qj - qi:
return False
return True # 여기까지 왔다면, True를 반환한다.
N = int(input())
queen_list = []
visited = [0]*N
cnt = 0
queen(0, N)
print(cnt)
Python으로는 실패했지만, Pypy3로 제출하니 성공했다!
여담이지만, 백준에서 이 문제의 힌트로 Queen의 음악이 있는데, 집이었다면 머리 흔들면서 코딩했을 것을 교육장에 나와있어서 아쉬운 마음이 들었다.
한달전에 백트랙킹을 간략하게 배우고, 더 공부하고 싶으면 이 문제를 풀어보세요! 라고 하셨었는데, 그 때에는 어떻게 풀어야 할 지 감도 못잡았었다.
한달 만에 이 코드도 뚝딱뚝딱 하고 쳐 낼 정도가 된 내 자신이 너무너무 뿌듯하다!!
Uploaded by N2T