[SWEA] 1974 스도쿠검증 (비트마스크)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq&categoryId=AV5Psz16AYEDFAUq&categoryType=CODE

SW Expert Academy

---

일단 풀이에 앞서..

내가 생각해낸 발상이 아니다. 나도 물어봐서 알게된거라..

난 되게 멍청하게 풀었었다. 근데 이렇게 하면 20x20 이어도 조금만 고치면 금방 검증이 가능하겠다고 생각했다.

xxx님 감사합니다. 역시 문제양에서 나오는 바이브가 있는것 같기도..

#include<cstdio>
#include<cstring>
typedef long long ll;
using namespace std;
int board[10][10];
void solve(int i)
{
	int result = 0;
	int sero[10]={0,};
	int m_board[10]={0,};
	int m_sum =0;
	for(int x = 0; x < 9; x++)
	{
		result = 0;
		m_sum = 0;
		for(int y = 0; y < 9; y++)
		{
			result |= 1 << board[x][y]; // 가로 체크
			sero[y] |= 1 << board[x][y]; // 세로 체크  
			m_board[y] |= 1 << board[x][y];
		}
		
		if(result != 1022)
		{
			printf("#%d 0\n",i+1);
			return;
		}
		//3x3 체크 (5x5면 % 5 하면 됨) 
		// x+1 %3 을 해서 틀린걸 못찾고 있었음. (x+1) % 3 을 해야하는데.. 
		if( (x+1) % 3 == 0){
			for(int z = 0; z < 9; z+=3){
				m_sum = m_board[z] | m_board[z+1] | m_board[z+2];
				m_board[z] = 0; m_board[z+1] = 0; m_board[z+2] = 0;
				if(m_sum != 1022)
				{
					printf("#%d 0\n",i+1);
					return;		
				}
			}
		}	
	}
	
	for(int z = 0; z < 9; z++){
		if(sero[z] != 1022){
			printf("#%d 0\n",i+1);
			return;
		}
	} 
	printf("#%d 1\n",i+1);
	return;

}
int main()
{
	int size;
	scanf("%d",&size);
	for(int i = 0; i < size; i++)
	{
		//c = c |  1 << elem
		for(int x = 0; x < 9; x++)
		{
			for(int y = 0; y < 9; y++)
			{
				scanf("%d",&board[x][y]);
			}
		}
		
		solve(i);	
	}
	return 0;
 } 

풀이 방법 :

가로 , 세로, 3x3 을 검증하면 되는데

​

하나의 행이 끝나면 -> 가로검증

행이 0, 3, 6 일때 -> 3x3 검증

다 끝나면 미리 받아뒀던 배열로 -> 세로 검증 을 했다.

O(n^2)이다.

​

1~9까지 숫자가 다 들어가있는지 검증하는걸 비트를 이용해서 했다.

예전에 이런거 비슷한거 하나 풀었는데 그때는 뭐 숫자로 바꿔서 1234567890 이렇게 했던것 같다.

​

result = result | ( 1 << 숫자) 이 방식을 이용하는건데..

이런 느낌이다.

천천히 써보면서 이해하면 할 수 있을것이다. 숫자가 한가지라도 비게 되면 1022보다 작기 때문에 오류라고 하면 된다.

이걸 좀 더 연장해보면

20 x 20이면

1부터 20까지 다 있나 보려면

2^20 - 2가 될 것이다. why? 최대 20칸 왼쪽으로 shift 하고나서, LSB는 0이니까..

​

실수한것 :

(x + 1 ) % 3 == 0 을 아무생각없이 x+1 % 3 ==0 으로 해서 왜 틀린지 못찾았다.

아무리봐도 틀린게 없는데 하나하나 찍어보다가 찾았다. 연산자 우선순위 잘 고려해서 해야지..

​

비트마스크를 직접 써본건 처음이었다.

나중에도 이렇게 겹치지않는 숫자 같은거 찾을때 써야겠다. 굉장히 편리하고 속도도 빠른 방법인것 같다.

​

=END

​