gaelim   3년 전

BFS를 이용하여 문제를 해결하려고 했습니다.


따라서, 상태저장을 어떻게 할까 생각을 했는데 

테이블이 1 01 01 01 01 01 0 ... 로 이진수처럼 채워되니까 어쨌든 1행 1열부터 시작해서 쭈욱 이진수를 긁어오면 정수로 변환가능하기에

그렇게 해줘서  chk 배열을 만들려고보니까, 메모리가 1기가가 훌쩍넘어버립니다.


밑에 코드는 chk 배열이 [1LL<<36] 인데 생각해보니 

1000101010... 이 최대 18* 18 이므로 총 [1LL<<(18*18)] 로 되어야하겠네요.


최대한 줄여보려고 생각해보아도.. 좌우 대칭일 때라던가, 상하 대칭, 대각 대칭의 경우를 줄여도 (총 4가지 경우) 어쨋든 상태는 1111100010101010 ... 식으로 저장되어야하니까 chk 배열이 결국엔 [1LL<<(18*18)]로 저장되어야하는거같습니다..

이럴땐 어떻게 해야할까요.?...


poirin   3년 전

https://www.acmicpc.net/board/...  

2^(18*18)의 경우의수가 있기 때문에 BFS로는 무리가 있을 것 같습니다.

3587jjh님이 답변해주신 내용입니다. 참고하시면 될 것 같습니다~

gaelim   3년 전

감사합니다..

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