[백준/C++] 9663 N-Queen (G4)

출력값은 올바르게 나오는데 계속 6%에서 틀렸다고 해서 오랫동안 고민했다. 시간 초과면 몰라도 틀렸다고 하는 이유를 알 수 없었다. 질문글들을 찾아보다가 출력값이 모두 올바른데 틀렸다는 것은 index 범위 오류라던가 메모리 초과 오류 등 Undefined Behavior와 관련있을 것이라는 댓글을 보았고 내 코드에서 그럴 위험이 있는 부분들을 생각해보았다.

 

<수정 전 코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using  namespace std;


// 퀸 후보 위치 선정 후 조건 만족하는지 확인 -> 수직/대각 연장선상에 퀸이 없는지 확인(n*n개 중 n개를 선정하는 모든 경우의 수를 반복)
// OR 후보 위치를 선정할 때 한 위치 선정하면 그 다음은 앞선 퀸의 수직/대각 연장선을 피해서 선정 => 반복?
int cnt = 0;
int n;
//vector<pair<int, int>> vec;

void Recursion(int line, bool visited[], int pair[][15])
{
	if(line == n)
	{
		cnt++;	
		
		return;
	}
	
	for(int i = 0; i < n ; i++)
	{
		if(visited[i] == true)
			continue;
		
		bool diagonal = false;
		
		for(int j = 0; j < line; j++ ) //pair에 들어있는 좌표들과 자신을 비교 -> 대각선상으로 겹치는지 확인
		{
			if(abs(pair[0][j] - line) == abs(pair[1][j]-i))
			{
				diagonal = true;
				break;
			}
		}
		
		if(diagonal)
			continue;
		
		visited[i] = true;	
		pair[0][line] = line;
		pair[1][line] = i;
		
		
		Recursion(line+1, visited, pair);
		
		visited[i] = false;
		
	}
}


int main(void)
{
	cin >> n;
	
	int pair[2][15] = { 0, };
	bool visited[n];
	
	Recursion(0,visited,pair);
	
	cout << cnt;
}

 

위의 코드에서 main 함수의 visited 배열 선언부를 수정하자 통과할 수 있었다.

bool visited[n]= { };

 

bool 배열 n크기 만큼에 초기화를 해주지 않아서 오류가 발생할 가능성이 생긴 것이다. 전에도 비슷하게 작은 초기화 문제로 계속 틀렸다고 해서 엄청 시간을 뺏긴 적이 있었다. 특별한 제한 조건 없이 가능한 상황이라면 배열은 무조건 초기화 해놓고 생각해야겠다.