9663 N-Queen (C#) [Gold IV]

 

풀이 방법

해당 문제는 완전 탐색을 통해 풀이해야 합니다.

모든 경우의 수를 하나하나 탐색하여 퀸을 놓을 수 있는지 체크하고, 개수를 저장하고 출력하면 됩니다.

 

---

힌트 1

퀸은 상, 하, 좌, 우로 이동할 수 있습니다.

즉, 현재 놓으려는 위치의 Y값과, X값을 사용하는 다른 퀸이 존재한다면, 그 자리는 놓을 수 없는 자리입니다.

그렇기에 Y값 하나에 1개씩, X값 하나에 1개씩 밖에 퀸을 둘 수가 없습니다.

 

힌트 2

퀸은 대각선으로도 이동할 수 있습니다.

즉 퀸A에 퀸B의 위치값을 뺄 때, 방향 벡터 X와 Y의 절대값이 같다면 대각선에 위치한다는 의미이기 때문에

놓을 수 없는 경우의 수 입니다.

 

힌트 3

최대 15개의 퀸을 15 * 15개의 체스판에 모두 배치하는 모든 경우의 수를 탐색할 때,

반복문을 어떻게 배치해야할지 어려움을 겪는 분들이 계실것 같습니다.

 

해당 문제는 반복문만을 사용하는 문제가 아니라 재귀함수를 활용해야하는 문제입니다.

입력값으로 15가 들어올 때에는 15중 For문을 돌려야하는 문제이기 때문에

반복문만을 사용하기에는 한계가 있습니다.

 

 

---

정답 코드

using System;
using System.Collections.Generic;
using System.Linq;

namespace Alroghtim_CS
{
	class Program
	{
		static int N;
		static int answer = 0;
		static List<(int, int)> pos = new List<(int, int)>();

		static bool CanReachDestination(int ay, int ax, int by, int bx)
		{
			if (ay == by)
				return true;
			if (ax == bx)
				return true;

			if (Math.Abs(ay - by) == Math.Abs(ax - bx))
				return true;

			return false;
		}


		static void Search(int y = 0)
		{
			if (pos.Count == N)
			{
				answer++;
				return;
			}

			for (int x = 0; x < N; x++)
			{
				bool flag = true;
				foreach ((int ay, int ax) in pos)
				{
					if (CanReachDestination(ay, ax, y, x))
					{
						flag = false;
						break;
					}
				}
				if (!flag) continue;

				pos.Add((y, x));
				Search(y + 1);
				pos.RemoveAt(pos.Count-1);
			}
		}


		static void Main(string[] args)
		{
			pos = new List<(int, int)>();
			answer = 0;
			N = int.Parse(Console.ReadLine());

			Search();

			Console.WriteLine(answer);
		}
	}
}