[C] 9663: N-Queen

구현은 다음과 같이 진행했다.

1. 퀸이 놓이면 퀸이 공격할 수 있는 자리들에 chess배열에 1을 추가하여(색칠하여) 저장하였다.

1-1.이때 가로 세로는 그냥 칠하고 (겹치는거 빼줌), 대각선을 색칠할 때는 while문을 이용하여 색칠해줬다. 이때 색칠하는 방법은 전에 풀었던 "토마토"문제와 같이 미리 x,y좌표로 갈 수 있는 경우의 수를 배열로 저장하고 (x,y_coordinate) for문을 이용해 구현했다.

1-2 이때 그래프의 범위를 벗어나면 for문을 빠져나오도록 했다

 

2. 이후 빈 공간에 queen을 배치할 수 있는지 판단하고 배치 가능하면 color함수를 재귀적으로 호출한다. 

2-1. 이때 계속 덧칠하면서 color을 호출했기 때문에 호출 후 return하면 다시 지워주기 위한 remove_color을 호출했다.(1을 빼줌)

 

3. 마지막으로 return 조건을 추가하고 이때 n과 queen의 개수가 같으면 cnt를 증가시켜줬다.

 

여기서 생각해야했던건 이중 for문으로 queen을 넣을 수 있는지 굳이 확인할 필요가 없었다.

어차피 n개의 queen을 넣어야하니까 한줄당 최대 1개만 배치 가능하므로 그냥 for문 하나만 사용하여

연산횟수를 줄일 수 있었다.

토마토 문제를 나름 응용하여 잘 풀었고 backtracking을 할때는 항상 재귀적으로! 그리고 재귀를 갖다오고나서 초취를 취해야한다면 return 하자마자 써줘야한다!!

 

아래는 소스코드이다!!

 

#include <stdio.h>
int chess[15][15];
int x_coordinate[4]={1,1,-1,-1};
int y_coordinate[4]={1,-1,1,-1};
int queen=0,cnt=0;

void remove_color(int y, int x, int n)
{
   for(int i=1;i<=n;i++) //가로 세로 색칠 지움
    {
      chess[y][i]--;
      chess[i][x]--;
    }
  chess[y][x]++; //한번 겹치는걸 더해줌
  
  for(int i=0;i<4;i++) //대각선 색칠자움
    {
      int nx=x;
      int ny=y;
      while(1)
        {
          nx+=x_coordinate[i];
          ny+=y_coordinate[i];
          if(nx>n ||ny>n||nx<1||ny<1) // 범위를 벗어나면 그만!
            break;
          
          chess[ny][nx]--;
        }
    }
}

void color(int y, int x, int n)
{
  //가로 세로 색칠
  for(int i=1;i<=n;i++) 
    {
      chess[y][i]++;
      chess[i][x]++;
    }
  chess[y][x]--; //한번 겹치는걸 빼줌

   //대각선 색칠
  for(int i=0;i<4;i++)
    {
      int nx=x;
      int ny=y;
      while(1)
        {
          nx+=x_coordinate[i];
          ny+=y_coordinate[i];
          if(nx>n ||ny>n||nx<1||ny<1) // 범위를 벗어나면 그만!
            break;
          
          chess[ny][nx]++;
        }
    }

  //재귀를 돌게하는 코드, 빈 공간에 queen을 넣을 수 있는지 판단
  int finish_cnt=0;

  if(y==n)
  {
    if(queen==n)
      cnt++;
    return;
  }

   for(int i=1;i<=n;i++)
   {
     if(chess[y+1][i]==0)
      {
        queen=queen+1; //*(queen)+1 개의 queen이 현재 체스판에 올려져있음
        color(y+1,i,n);
        queen=queen-1; //하나 다시 뺌
        remove_color(y+1,i,n); //reutrn 하고 돌아올때 다른 경우의 수를 찾기 위해 방금 색칠한 부분을 다시 없애준다.
        }
      else
        finish_cnt++;
   }  

  //맨끝까지 갔다!, 종료조건!
  if(finish_cnt==n*n )
  {
    if(queen==n){
      cnt=cnt+1;
    }
    return;
  }
  
    
}



int main(void)
  {
    int n;
    scanf("%d",&n);
    
    for(int i=1;i<=n;i++)
     {
        queen++;
        color(1,i,n);
        queen--;
         remove_color(1,i, n);            
      }   
    
    printf("%d",cnt);   
    
  }