9663번 N-Queen

문제링크 : www.acmicpc.net/problem/9663

9663번: N-Queen

---

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 

8

예제 출력 1

92

---

<알고리즘>

 1) 한 행씩 내려가면서 각 행에 queen 놓기 => 같은 행에 2개 이상 들어갈 수 없음

 2) 각 행에 놓은 queen의 위치가 앞선 queen들의 위치와 비교하여 조건에 해당하지 않는 곳이 있는지 확인

    => 대각선상에 놓여 있는지(가로 세로 길이 비교로 확인), 같은 열에 놓여있지 않은지

 3) 끝 행까지 queen을 놓았다면 경우의 수 하나가 확보되었음을 저장하고 백트래킹 실시

 

 

 

<구현>

 1) index를 증가시키면서 0 ~ N번째 행까지 함수 반복 

 2) 우선 queen이라는 배열(각 행 = index, queen이 놓인 위치 = value 인 배열)이용

    for문을 이용하여 index행에 i번째 열에 queen을 놓기

    check하는 함수를 이용하여 해당 index의 queen이 이전 queen들의 위치와 비교하여 조건에 만족하는지 확인

    2-1) 조건에 만족한다면 index를 증가시켜 다음 행에 놓을 queen의 위치 구상

    2-2) 조건에 만족하지 않는다면 해당 index의 queen을 내려놓음(초기화 값으로 변경)

 3) index == N이 되면 즉, 마지막 행까지 조건에 맞게 queen을 놓았다면 cnt 증가

    return을 통해 백트래킹 실시 => index가 하나 줄어들고 2)에서 사용한 for문의 i가 증가, 2~3번 과정 반복

 

 

 

 

 

메모리 : 2016KB    시간 : 4352ms

#include <iostream>
#include <algorithm>
using namespace std;

int queen[15] = { -1, };
int cnt = 0;

bool checking(int index) {
	if (index == 0) return true;
	else {
		for (int i = 0; i < index; i++) {
			//같은 라인일때
			if (queen[i] == queen[index]) return false;
			//대각선 상에 존재할 때
			else if (abs(queen[index] - queen[i]) == index - i) return false;
		}
	}
	return true;
}

void chess(int index, int N) {
	if (index == N) { 
    	++cnt;
        return;
    }
	else {
		for (int i = 0; i < N; i++) {
			//i값을 채용
			queen[index] = i;
			//i값이 조건에 만족했다면 다음 level로 진출
			if (checking(index)) chess(index + 1, N);
			//i값 채용 취소
			queen[index] = -1;
		}
	}
}

int main() {
	int N = 0;
	cin >> N;

	chess(0, N);
	cout << cnt;
	return 0;
}

 

 

 

+) 전에 실패한 방식 => 고려할조건을 너무 복잡하게 잡았음, 체스판을 통으로 구현할 필요가 없음=구현복잡,메모리 차지

chess = [[False for i in range(15)]for j in range(15)]
count =0
def deleteC(x,y,N):
    global chess
    for i in range(N):
        chess[x][i] = True
        chess[i][y] = True
    copyX = x
    copyY = y
    while((copyX>-1) & (copyY>-1)):
        chess[copyX][copyY] = True
        copyX-=1
        copyY-=1
    copyX = x
    copyY = y
    while((copyX<N) & (copyY<N)):
        chess[copyX][copyY] = True
        copyX+=1
        copyY+=1
    copyX = x
    copyY = y
    while ((copyX >-1) & (copyY < N)):
        chess[copyX][copyY] = True
        copyX -= 1
        copyY += 1
    copyX = x
    copyY = y
    while((copyX<N) & (copyY>-1)):
        chess[copyX][copyY] = True
        copyX+=1
        copyY-=1

def check(N, nowQ):
    global count
    global chess
    for i in range(0,N):
        for j in range(0,N):
            if (nowQ==N):
                count+=1
                chess = [[False for i in range(15)]for j in range(15)]
                nowQ=0
            elif(chess[i][j]==False):
                chess[i][j] = True
                nowQ+=1
                deleteC(i,j,N)
                print(chess)
                #check(N, nowQ)
import sys
N = int(sys.stdin.readline())
check(N,0)
print(count)