[ALGOSPOT] NQUEEN - Zipper의 활용

문제: https://algospot.com/judge/problem/read/NQUEEN

N의 범위가 1≤N≤12인 간단한 문제...인데 그냥 백트래킹으로 짜니까 시간 초과 ㅜㅜ

일단 n-queen 알고리즘과 무관한, 문제 입력을 처리하는 코드부터 작성한다.

import Control.Monad

main = do

n <- read `fmap` getLine :: IO Int

forM_ [1..n] $ const $ do

x <- read `fmap` getLine :: IO Int

print $ nqueen x

이제 N을 입력받아 답의 개수를 반환하는 nqueen 함수를 작성하면 된다.

NN개의 칸에 N개의 퀸을 놓는 모든 경우의 수를 따지는 건 너무 어리석은 짓이고.. 각 행에 퀸이 하나씩만 들어갈 수 있으므로 각 행의 모든 열에 놓아보는 방법을 쓴다. n-queen의 가장 기초적인 해법이다.

import Data.List

import Data.Array

empty n = array (1,n) [(i,0) | i<-[1..n]]

nqueen n = fill (empty n) 1 1 0 where

fill board row col cnt = case () of

()  | row > n -> fill (board // [(n,0)]) (n-1) (board!(n-1) + 1) (cnt+1)

| col > n -> if row==1 then cnt else fill (board // [(row-1, 0)]) (row-1) ((board!(row-1)) + 1) cnt

| peace -> fill (board // [(row,col)]) (row+1) 1 cnt

| True -> (fill board row (col+1) cnt)

where

peace = (row==1) || False == (foldl1' (||) [(board!i) `elem` [col,col+i-row,col+row-i] | i <- [1..(row-1)]])

정말 이 혼돈의 끝은 어디일까

사실은 (http://en.wikibooks.org/wiki/Algorithm_Implementation/Miscellaneous/N-Queens)의 C++ 코드와 똑같은 로직이다. 이쪽이 훨씬 알아보기 쉬울 것이다.

하지만 위의 nqueen 함수는 치명적인 문제가 있는데, Array 모듈을 사용한다는 것이다. 하스켈의 배열은 읽기는 O(1)이지만 쓰기는 O(N)이라는 흉악한 성능을 자랑하는데 분기 4개 중 3개에서 쓰기를 수행한다. N = 12면 시간 초과를 피할 수 없다.

하스켈도 mutable array를 모나드 형태로 지원하기 때문에 관련 자료를 찾아볼까 했지만 마침 지퍼(Zipper)가 생각났다. 거창하게 지퍼라 할 것도 없이, (지금까지 놓은 퀸의 리스트 + 현재 퀸)을 보관하면 된다. 이 때 리스트는 역순으로 저장되어, 바로 전에 놓은 퀸이 리스트의 맨 앞에 온다. 백트랙을 할 때 무조건 바로 위의 행으로 돌아가기 때문에 바로 리스트의 헤드를 취하면 된다.

import Data.List

data Zipper = Zipper [Int] Int

emptyZipper = Zipper [] 1

zqueen n = zfill emptyZipper 1 0 where

zfill (Zipper [] col) row cnt = if col > n then cnt else zfill (Zipper [col] 1) (row+1) cnt

zfill (Zipper prev@(prevh:prevt) col) row cnt = case () of

()  | row > n -> zfill (Zipper prevt (prevh+1)) n (cnt+1)

| col > n -> if row==1 then cnt else zfill (Zipper prevt (prevh+1)) (row-1) cnt

| peace -> zfill (Zipper (col:prev) 1) (row+1) cnt

| True -> zfill (Zipper prev (col+1)) row cnt

where

peace = diag prev 1 col

diag [] _ _ = True

diag (c:cs) i col = if c==col || c-col==i || col-c==i then False else diag cs (i+1) col

Data.Array 모듈을 완전히 제거했다. 컴파일한 상태에서 속도 측정하는 방법은 아직 모르겠고 ghci에서 비교해보니 N = 12일 때 zqueen이 nqueen보다 약 4배 빨랐다. 저지 시스템은 실행시간 501ms으로 통과. 똑같은 로직을 c++로 대충 짜면 5배 빠르다(...)