글 읽기 - 스도쿠 문제 입력 값이 변하는 이유가 무엇일까요/

roro7773 5년 전 0

안녕하세요.

스도쿠 문제를 풀려고 코드를 짰습니다.

비트마스크를 활용해서 (i,j)원소의 값을 구해야 할 경우 (i,j)에 해당하는 열, 행, 그리고 정사각형으로 구성된 구역 각각에서 1~9 숫자중 없는 것을 각각 비트마스크로 표현을 하여 문제를 풀려고 계획했습니다. 그런데 코드의 적합성을 확인하기 전에 자꾸 입력의 값이 틀려지는 문제가 발생하였습니다.;;

소스코드에서 sheet[15][15]에 문자를 입력하게 됩니다. 그런데 입력후 112번째 줄을 통하여 입력한 것을 그대로 확인해보면

sheet[0][0]의 값만 벼경이됩니다. 예를 들어 문제의 예시처럼 첫줄에 0 3 5 4 6 9 2 7 8 을 넣을 경우 출력되는 값이 96 3 5 4 6 9 2 7 8 이 됩니다. 다른 행의 0값은 제대로 출력이되구요. 그리고 이 현상은 102번째 줄에 AddCheck(i, j, sheet[i][j]); 를 실행하지 않으면 문제 없이 출력이 됩니다. AddCheck(i, j, sheet[i][j]);는 (i,j)에 값을 넣었을 경우(ex, sheet[i][j]=3;) 각 행, 열, 그리고 작은 정사각형에 넣은 입력값 (즉 '3') 이 비트마스크로 표시가 되는 함수입니다.

혹시 왜 이런 현상이 발생하는 것일까요..ㅜㅜ

알려주시면 감사하겠습니다..

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>

using namespace std;

int checkCol[9] = { 0 }, checkRow[9] = { 0 }, checkSec[9] = { 0 };  // 전역 변수. bitmask로 
int sheet[9][9] = { 0 };

void AddCheck(int i, int j, int x)
{
	checkRow[i] = checkRow[i] | (1 << (x - 1));    // checkRow에 x값 표현
	checkCol[j] = checkRow[j] | (1 << (x - 1));    // checkRow에 x값 표현
	checkSec[3 * i / 3 + j / 3] = checkSec[3 * i / 3 + j / 3] | (1 << (x - 1));    // checkRow에 x값 표현
}
void RemoveCheck(int i, int j, int x)
{
	checkRow[i] = checkRow[i] & ~(1 << (x - 1));    // checkRow에 x값 표현
	checkCol[j] = checkRow[j] & ~(1 << (x - 1));    // checkRow에 x값 표현
	checkSec[3 * i / 3 + j / 3] = checkSec[3 * i / 3 + j / 3] & ~(1 << (x - 1));    // checkRow에 x값 표현
}


void solve(int row, int col)
{
	cout << row << " , " << col << "  :  " << sheet[row][col] << '\n';
	// 답을 찾았을 때!
	if (row == 9)
	{
		for (int i = 0; i<9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				cout << sheet[i][j] << " ";
			}
			cout << '\n';
		}
		return;
	}

	// 답 적는 곳이 아닌경우  --> 다음 칸을 봅시다.
	if (sheet[row][col] > 0)
	{
		if (col < 8)
			solve(row, col + 1);
		else if (col == 8)
			solve(row + 1, 0);
	}

	// sheet 값이 0인경우 결국 답을 찾아야한다
	else
	{

		// 조건에 맞는 집합을 찾아낸다. or 연산으로 3개 모두에서 비어잇는 집합
		// candidate에 0인 bit가 가르키는 값이 답의 후보이다.
		int candidate = checkRow[row] | checkCol[col] | checkSec[3 * row / 3 + col / 3];

		// 정답 후보가 없는 경우. 즉 오답의 경우
		if (candidate == (1 << 9) - 1)
		{

			return;
		}

		else
		{
			for (int i = 1; i <= 9; i++)
			{
				if ((candidate & (1 << (i - 1))) == 0) // i 값이 후보인 답후보인경우
				{
					sheet[row][col] = i;
					AddCheck(row, col, i);

					//다음 장에 답적기
					if (col < 8)
						solve(row, col + 1);
					else if (col == 8)
						solve(row + 1, 0);
					sheet[row][col] = 0;
					RemoveCheck(row, col, i);
				}
			}
		}
	}

}

int main()
{
	ios::sync_with_stdio(false);

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{

			cin >> sheet[i][j];

			if (sheet[i][j] != 0)
			{
				AddCheck(i, j, sheet[i][j]);
			}
	
		}

	}




	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << sheet[i][j] << " ";

		}
		cout << '\n';
	}

	// 재귀함수 알고리즘 
	//solve(0, 0);


	cout << sheet[0][0];
	return 0;
}

rhs0266 5년 전 1

3 * row / 3 + col / 3

이 값이 9 이상일 수 있는데, checkSec 배열을 넘어가는 인덱스를 참조하는 과정에서 다른 메모리를 건드리고, 그게 입력 배열 까지 영향을 끼친 것 같습니다.

roro7773 5년 전 0

덕분에 잘 해결되었습니다. 정말 감사합니다!

배열을 다룰 때는 조심해야겠네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

스도쿠 문제 입력 값이 변하는 이유가 무엇일까요/

roro7773 5년 전 0

rhs0266 5년 전 1

roro7773 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말