[9663] - N-Queen

https://www.acmicpc.net/problem/9663

9663번: N-Queen

이 문제는 풀다가 구현을 하지 못해서 구글링을 통해 풀이방법을 알게 되었다.

처음 풀 때 아이디어는, 퀸은 가로,세로 대각선으로 움직일 수 있으니 2차원 배열로 체스판을 만들어 구현하려 하였다.

구현하려 했던 아이디어

- 가로 세로는 배열의 인덱스가 같으면 패스

- 대각선은 우상향 대각선과 우하향 대각선으로 나누어 판별 후 대각선일 시 패스

   - 우상향 대각선은 점들의 x+y값이 같음

   - 우하향 대각선은 점들의 x-y값이 같음

위와 같이 구현하려 했지만 감이 잡히질 않았다.

 

문제 풀이

구글을 통하여 알게된 풀이 - 주석에 설명을 자세히 써 놓았다.

1. 인덱스를 행, 인덱스에 해당하는 값을 열로 표현

2. 행이 주어진 n 만큼 차면 카운트 증가

3. 같은 행,열, 대각선에 퀸이서로 존재하면 안됨

4. 조건을 만족할 시 재귀를 통해 다음 행으로 이동

using System;
using System.Collections.Generic;
using System.Text;

namespace Baekjoon.Gold
{
    class _9663
    {
        static int n;
        static int count = 0;
        static int[] chess;
        //static StringBuilder stb = new StringBuilder();
        static void Main(string[] args)
        {
            n = int.Parse(Console.ReadLine());
            chess = new int[n];
            queen(0);
            Console.WriteLine(count);
            //Console.WriteLine(stb);
        }

        static void queen(int num)
        {
            if(num == n)
            {
                count++;
                return;
            }

            //num = 행값 , i = 열값
            //즉 chess[num] = 0 이면 num행, i열에 퀸을 두었다는 뜻
            for(int i = 0; i< n; i++)
            {
                chess[num] = i;
                bool put = true;
                //stb.AppendLine(String.Join(" ", chess));
                //현재 만약 5번째 행이면 0~4행들 검사
                for (int j = 0; j<num; j++)
                {
                    //같은 행에 있으면 안됨.
                    if (chess[num] == chess[j])
                    {
                        put = false;
                        break;
                    }
                    //두 점의 열의 차, 행의 차의 절대값이 같으면 대각선임
                    //ex1) 우하향 대각선 -> (1,2) (2,3) (3,4) (4,5)
                    //ex2) 좌하향 대각선 -> (1,5) (2,4) (3,3) (4,2) 
                    //절대값(x1 - x2) = 절대값(y1 - y2)가 전부 같다.
                    //퀸은 행,열,대각선으로 움직이니 대각선에도 있으면 안된다.
                    else if (Math.Abs(chess[j] - chess[num]) == Math.Abs(j-num))
                    {
                        put = false;
                        break;
                    }
                }

                if (put)
                    queen(num + 1);
            }
        }
    }
}

조건 구현하기가 힘든 문제였다..