C++) 프로그래머스 풀이_N-Queen

https://programmers.co.kr/learn/courses/30/lessons/12952?language=cpp#

코딩테스트 연습 - N-Queen | 프로그래머스

백트래킹 공부를 하기 위해 집어든 문제

백트래킹은 말그대로 롤백하면서 세어나가야 하는데

값을 초기화하는 것을 깜빡했..다기 보다는 당연히 매개변수로 전달하고 있으니까

얘가 값이 변한게 초기화될 줄 알았다. 

Call by value가 아니였구나 이거? (무식)

 

무튼 재귀로 구현하는게 편하다.

갠적으로 재귀함수 구현하는 걸 좋아한다(tmi)

 

처음 접근을... 2차원 배열을 만들어서 하나하나 구하고 넘기고 구하고 넘기고 할 생각이였는데

2차원 배열을 만들면 저장공간이 늘어나는건 둘째치고

넘겨서 사용하기가 너무 귀찮고 계산도 많이 들어간다.

 

어짜피 같은 열 다른 행에는 Queen을 놓을 수 없으므로

배열로 열 하나만 만들고, count만 올려가며 다른 행 계산을 해준다.

 

한 행씩 넘어가면서 쭉쭉쭉 찾아보고, 모두 다 놓고나면 (size < count)가 되면 한 판을 완성했다는 의미로 ++ 을 해줌.

 

그렇게 한판씩 체크하고 롤백해서 올라가게끔 코드를 짜면 됩니다.

 

#include <string>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

//같은 열이나 대각선위에 놓인 Queen을 검사하는 함수
//매개변수 -> col, 전체size, 현재 놓으련ㄴ 위치, 몇 번째 열인지
//비어있으면 true return
bool CheckBlank(int col[], int size, int cur, int count)
{
	if (col[cur] != 0)
		return false;
	for (int i = 1; i <= size; ++i)
	{
		if (col[i] != 0 && abs(cur - i) == abs(count - col[i]))
			return false;
	}

	return true;
}

int SetQueen(int col[], int size, int count)
{
	int result = 0;

	if (size < count)
	{
		result++;
	}
	else
	{
		for (int i = 1; i <= size; ++i)
		{
			if (CheckBlank(col, size, i, count))
			{
				col[i] = count;
				result += SetQueen(col, size, count + 1);
				col[i] = 0 ;
			}
		}
	}

	return result;
}

int main()
{
	int size, answer = 0;
	cin >> size;
	int col[13] = { 0, };

	for (int i = 1; i <= size; ++i)
	{
		memset(col, 0, sizeof(int) * 13);
		col[i] = 1;
		answer += SetQueen(col, size, 2);
	}

	cout << answer << endl;
}