99클럽 코테스터디 16일차 TIL N-Queen

N-Queen

프로그래머스 level 2 완전탐색

문제설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항
퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
n은 12이하의 자연수 입니다.

문제풀이

예전에 고생해서 풀었던 문제라서 오랫만에 보니까 좀 반가웠다. 그때 거의 2주 가까이 풀이했던 기억이 있다.

 

파이썬으로 이미 풀이가 되어있어서 C++ 로 다시 한번 풀어봤다.

 

별다른 처리 없이 체스의 Queen의 특성을 조건으로 만들어주고, 정직하게 구현하면 풀리는 문제다.

 

체스판은 좌우 대칭이므로 반절만 탐색하고 두배를 해주면 답이 나온다.

 

n 이 홀수일 경우는 따로 만들어 탐색해줬다.

 

Python 코드

예전에 작성했던 파이썬 코드에는 공부하면서 작성해서 그런지 한줄한줄 주석이 달려있었다.

"""
좌우 대칭 이므로 반으로 반쪽만 계산해주고 두배 해주면가능
가운대가 있는 경우엔 그 부분만 따로 계산
"""
# 재귀함수로 구현
def set_q(x,y, fld, n):
    global cnt
    global cnt_center

    # 체스판 밖이면 함수 종료
    if x == n:
        return

    # 첫번째 행은 유효성 체크를 할필요 없음
    if x == 0:
        # 대칭이므로 중간 까지만 진행
        for y_idx in range(n//2):
            fld[x][y+y_idx] = 1
            set_q(x+1, y, fld, n)
            fld[x][y+y_idx] = 0

        # 홀수일 경우 추가로 확인
        if n%2:
            if n == 1:
                cnt_center += 1
                return
            fld[x][n//2] = 1
            mono_set_q(x+1, y, fld, n)

    else:
        # 한칸씩 옆으로 이동하며 체크
        for y_idx in range(n):
            # 해당 위치가 가능할 때, 첫번째 행에서는 가능한지 확인하지 않아도 되므로
            if ck_avail(x, y_idx, fld, n):
                # 끝의 행에서 가능한 자리를 찾은 경우 더이상 같은 행에는
                # 없으므로 return 해 그 함수를 종료한다
                if x == n-1:
                    cnt += 1
                    return
                else:
                    # 아래 행으로 내려오기 전에 해당 위치를 1로 바꿔준다
                    fld[x][y_idx] = 1
                    # 다음 행으로 내려가서  탐색
                    set_q(x+1, y, fld, n)
                    # 끝난 뒤 자리를 비워준다
                    fld[x][y_idx] = 0


# 홀수는 따로 추가탐색
def mono_set_q(x, y, fld, n):
    global cnt_center

    for y_idx in range(n):
        # 해당 위치가 가능할 때, 첫번째 행에서는 가능한지 확인하지 않아도 되므로
        if ck_avail(x, y_idx, fld, n):
            # 끝의 행에서 가능한 자리를 찾은 경우 더이상 같은 행에는
            # 없으므로 return 해 그 함수를 종료한다
            if x == n-1:
                cnt_center += 1
                return
            else:
                # 아래 행으로 내려오기 전에 해당 위치를 1로 바꿔준다
                fld[x][y_idx] = 1
                # 다음 행으로 내려가서  탐색
                mono_set_q(x+1, y, fld, n)
                # 끝난 뒤 자리를 비워준다
                fld[x][y_idx] = 0


# 가능한지 확인하는 함수
def ck_avail(x, y, fld, n):
    # 위에서부터 퀸을 놓으면서 내려오니까 위에 세 방향만 확인
    for mi, mj in [[-1, 0], [-1, 1], [-1, -1]]:
        # di, dj를 기본값으로 세팅해준뒤
        di, dj = x, y
        while 1:
            # 한칸씩 위로 올라가며 확인한다
            di, dj = di + mi, dj + mj
            if 0 <= di <n and 0 <= dj < n:
                # 해당 구역이 채워져 있다면
                # 이 위치는 불가능 하다고 판단하고 return
                if fld[di][dj]:
                    return False
            # 체스판 밖으로 나가면 break
            else:
                break
    # 끝까지 돌면 True를 반환한다
    return True

cnt = 0
cnt_center = 0
def solution(n):
    global cnt
    global cnt_center

    answer = 0
    # 비어있는 체스판 생성
    chess_fld = [[0]*n for _ in range(n)]
    # 경우의 수를 세어줄 변수 선언
    set_q(0, 0, chess_fld, n)
    answer = (2*cnt) + cnt_center
    return answer

 

C++ 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int cnt = 0, cnt_center = 0;
bool fld[12][12] = {false, };
int mx[] = {-1, -1, -1};
int my[] = {0, 1, -1};

bool condition (int x, int y, int n) {
    return 0 <= x && x < n && 0 <= y && y < n;
}

bool ck_avail(int x, int y, int n) {
    for (int i=0; i<3; i++) {
        int dx = x, dy = y;
        while (true) {
            dx += mx[i];
            dy += my[i];
            if (condition(dx, dy, n)){
                if (fld[dx][dy]) return false;
            } else break;
        }
    }
    return true;
}

void mono_set_q(int x, int y, int n) {
    for (int y_idx = 0; y_idx < n; y_idx++) {
        if (ck_avail(x, y_idx, n)) {
            if (x == n-1) {
                cnt_center += 1; return ;
            }
            fld[x][y_idx] = true;
            mono_set_q(x+1, y, n);
            fld[x][y_idx] = false;
        }
    }
}

void set_q(int x, int y, int n) {
    if (x == n) return ;

    if (x == 0) {
        for (int y_idx = 0; y_idx < n/2; y_idx++) {
            fld[x][y+y_idx] = true;
            set_q(x+1, y, n);
            fld[x][y+y_idx] = false;
        }
        if (n%2) {
            if (n == 1) {
                cnt_center += 1;
                return;
            }
            fld[x][n/2] = 1;
            mono_set_q(x+1, y, n);
        }
    }
    else {
        for (int y_idx=0; y_idx < n; y_idx++) {
            if (ck_avail(x, y_idx, n)) {
                if (x == n-1) {
                    cnt += 1;
                    return;
                }
                else {
                    fld[x][y_idx] = true;
                    set_q(x+1, y, n);
                    fld[x][y_idx] = false;
                }
            }
        }
    }
}

int solution(int n) {
    int answer = 0;

    set_q(0, 0, n);

    cout << cnt << " " << cnt_center << "\n";
    answer += (2 * cnt) + cnt_center;
    return answer;
}

 

회고

Python 과 C++ 이 생각보다 더 문법이 많이 차이나고 Python의 경우는 확실히 사용하기 편한 언어인걸 다시 한번 알게되었다.

 

하지만, 글로벌 처리나, 이 변수가 어떤 변수인지는 한눈에 알 수 없어서 좀 불편한 부분이 있는 것 같다. 언어마다 장단점이 있는 것 같다.