가능한 풀이공간(?)이 2^16개이고 표현형이 2^16개인데 그 사이에 일대일대응이 있는 거 같은데
그러니까 해답은 유일한 거 아님?
16칸 중에 한 칸만 뒤집는 서로 다른 16개의 풀이를 미리 구해놓으면
우리가 원하는 모양의 풀이에서 뒤집을 부분에 해당되는 솔루션 골라서 전부 xor 돌리면 되지 않음?
그러니까 해답은 유일한 거 아님?
16칸 중에 한 칸만 뒤집는 서로 다른 16개의 풀이를 미리 구해놓으면
우리가 원하는 모양의 풀이에서 뒤집을 부분에 해당되는 솔루션 골라서 전부 xor 돌리면 되지 않음?
네 그러니까 2^16번만 체크하면 된다구요. 집합에서 부분집합의 XOR이 특정 수가 되는걸 찾는거랑 똑같은 문제니까요
미리 구하는거 16번이면 되는데 뭘
O(n^2)이 아니라 2^n 이겠죠
아 다시읽어보니까 무슨말 하는지 이해가 가는데. 그런데 한칸 뒤집는거의 솔루션이 없을때는 어쩌려고요?
한칸만 뒤집힌거의 솔루션은 없는데 여러칸 뒤집힌 경우의 솔루션이 있는 경우는 위의 알고리즘 적용할수가 없음. 그리고 미리 구하는 시간을 생각하는게 맞고요
아 안되네 깨갱
그래요 일대일대응이면 되겠죠. 그런데 일대일인거 증명이 있어야함
지금 생각해봤는데. 격자판이 짝수x짝수면 일대일인게 맞음
ㄴ사실 홀수일 때 일대일 아닌 건 알겠는데 짝수일 때 일대일 증명은 못 하겠네요
그리고 대칭이니까 16개 말고 4개만 구하면 될듯