문제

문제 링크

어떻게 접근할 것인가

  • 하나의 돌을 놓고 놓을 수 있는 돌을 찾아서 놓고 하는 식으로 진행했다.
  • 그래서 총 iteration을 다 돌았을 때 가능했던 횟수를 출력했다.

초기 코드(시간 초과)

#include <cstdio>
int n, cnt, arr[14][14];
int d[4][2] = { {1, -1}, {1, 1}, {-1, 1}, {-1, -1} };

void find(int x, int q){
    if(q == n){
        cnt ++;
        return;
    }
    for(int i = x; i < n; i++){
        for(int j = 0; j < n; j++){
            if(arr[i][j] == 0){
                bool isvalid = 1;
                for(int k = 0; k < n; k++){
                    if(arr[i][k] || arr[k][j]){
                        isvalid = 0;
                        break;
                    }
                }
                if(!isvalid)continue;
                for(int p = 0; p < 4; p++){
                    int t = 1;
                    while(1){
                        if(i + d[p][0]*t >= n || j + d[p][1]*t >= n || i + d[p][0]*t < 0 || j + d[p][1]*t < 0) break;
                        if(arr[i + d[p][0]*t][j + d[p][1]*t]){
                            isvalid = 0;
                            break;
                        }
                        t ++;
                    }
                }
                if(!isvalid)continue;
                arr[i][j] = 1;
                find(i, q+1);
                arr[i][j] = 0;
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    find(0, 0);
    printf("%d", cnt);
}
  • 시간 무진장 많이 걸린다.

개선잠

  • 어차피 한 줄에 하나씩 밖에 안들어 가니까 하나의 줄을 기준으로 되는 돌을 찾아보자.
  • 어레이도 2차원이 아니라 1차원으로 진행해도 된다.
  • 대각에 원소가 있는지, 해당 값과 같을 값을 가지는 어레이가 있는지 확인한다.

최종 코드

#include <cstdio>
#include <cmath>

int n, cnt, board[15];

void find(int x, int q){
    if(q == n){
        cnt ++;
        return;
    }
    
    for(int i = 1; i < n + 1; i++){
        int isvalid = 1;
        for(int k = 1; k < x; k++){
            if(board[k] == i || abs(x - k) == abs(i - board[k])) isvalid = 0;
        }
        if(isvalid) {
            board[x] = i; 
            find(x + 1, q + 1);
            board[x] = 0;
        }
    }
    
}

int main(){
    scanf("%d", &n);
    find(1, 0);
    printf("%d", cnt);
}

느낀점

  • 진짜 코드가 소름돋게 간결해졌다.
  • 이런 생각의 차이가 코드의 차이를 만들어 내는데 나도 육목을 짜보는데 있어서 이런 창의적인 발상이 있었으면 좋겠다.