[백준] 9663번 N-Queen (bk_9663)

N-Queen - 9663번

문제

• N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
• N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
• 제한시간 1초

입출력

# 입력
8
# 출력
92

생각한 알고리즘

1. 첫번째 알고리즘 (python3)
   1. 체스 퀸이 가면 안되는 위치(True or False)를 담는 이중배열 check_arr 생성
   2. 주의할점 : 이중배열 복사시 cpy = ori[:] 하면 기존/카피 배열 변경시 따라서 변경된다. 따라서 import copy cpy = copy.deepcopy(ori) 이용
   3. check_arr 에서 현재 기준 위치가 True 라면 해당 위치 기준으로 대각선 , 행 , 열에 위치한 배열 값을 False로 바꾼뒤 다시 함수를 n+1 번째의 퀸 위치를 탐색한다.
   4. 문제발생 : 함수 호출시 이중배열을 계속 부르고, 탐색하기 때문에 시간 초과 발생

# 퀸은 앞, 뒤, 대각선으로 움직임
# 백트래킹
import copy 

N = int(input())
count = 0

def back(check,n):
    global count
    check_arr = copy.deepcopy(check)
    if(n == N):
        count += 1
    else:
        for y in range(N):
            if(check_arr[n][y]):
                arr = copy.deepcopy(check)
                for i in range(N):
                    arr[n][i] = False
                    arr[i][y] = False
                i = 1
                while ( n + i < N or y + i  < N or n - i >= 0 or y - i  >= 0 ):
                    if (n + i < N and y + i  < N):
                        arr[n+i][y+i] = False
                    if (n - i >= 0 and y - i  >= 0):
                        arr[n -i][y-i] = False
                    if (n - i >= 0 and y + i  < N ):
                        arr[n -i][y+i] = False
                    if(n + i < N and y - i  >= 0 ):
                        arr[n +i][y-i] = False
                    i += 1
                future = True
                for i in range(n+1,N) :
                    if(not True in arr[i]):
                        future = False
                        break
                if(future):
                    back(arr,n+1)
                

# 이중 배열 초기화
arry = [[True]*N for _ in range(N)]

back(arry,0)
print(count)
            

1. 두번째 알고리즘 (python3)
   1. n 번째 퀸을 탐색중이라하면 이전의 0~n-1 번째 퀸의 위치 튜플을 담은 리스트 생성
   2. 현재 탐색중인 위치가 기존 퀸의 위치와 싸우지 않는 (save == 0) 위치라면 n+1 번째 퀸을 탐색한다.
   3. 문제발생: python3 자체가 너무 느리다.

# 퀸은 앞, 뒤, 대각선으로 움직임
# 백트래킹
# import copy 

N = int(input())
count = 0

def back(idx_list,n):
    idx_l = []
    for i in idx_list:
        idx_l.append(i)
    global count
    # idx_l = cpy_idx(idx_list)
    # idx_list = copy.deepcopy(idx_list)
    if(n == N):
        count += 1
    else:
        
        for y in range(N):
            save = 0
            tup = (n,y)
            for t in idx_list:
                if(t[0] == tup[0]):
                    save = 2
                    break
                elif(t[1] == tup[1]):
                    save = 1
                    break
                elif(abs(t[0]-tup[0]) == abs(t[1] - tup[1])):
                    save = 1
                    break
            
            if(save == 0):
                idx_l.append((n,y))
                back(idx_l,n+1)
                idx_l.pop()
            elif(save == 2):
                break

            
back([],0)
print(count)
            

1. 두번째 알고리즘 (c)
   1. n 번째 퀸을 탐색중이라하면 이전의 0~n-1 번째 퀸의 위치 튜플을 담은 리스트 생성
   2. 현재 탐색중인 위치가 기존 퀸의 위치와 싸우지 않는 (save == 0) 위치라면 n+1 번째 퀸을 탐색한다.

#include <stdio.h>
#include <stdlib.h>

int N;
int count = 0;

void back(int idx_list[][2], int n)
{
    if(n == N)
        count += 1;
    else
    {
        for(int y = 0; y < N; y++)
        {
            int save = 0;
            int tup[2] = {n,y};
            for(int i = 0; i < n; i++)
            {
                if(idx_list[i][0] == tup[0])
                {
                    save = 2;
                    break;
                }
                else if(idx_list[i][1] == tup[1])
                {
                    save = 1;
                    break;
                }
                else if((abs(idx_list[i][0] - tup[0])) == (abs(idx_list[i][1] - tup[1])))
                {
                    save = 1;
                    break;
                }
            }
            if(save == 0)
            {
                idx_list[n][0] = n;
                idx_list[n][1] = y;
                back(idx_list,n+1);
                idx_list[n][0] = 0;
                idx_list[n][1] = 0;
            }
        }
    }
}
int main()
{
    int tup_order[30][3] = { 0, };
    scanf("%d", &N);
    
    back(tup_order,0);
    printf("%d", count);
    return 0;
}