https://www.acmicpc.net/board/...
2^(18*18)의 경우의수가 있기 때문에 BFS로는 무리가 있을 것 같습니다.
3587jjh님이 답변해주신 내용입니다. 참고하시면 될 것 같습니다~
14927번 - 전구 끄기
https://www.acmicpc.net/board/...
2^(18*18)의 경우의수가 있기 때문에 BFS로는 무리가 있을 것 같습니다.
3587jjh님이 답변해주신 내용입니다. 참고하시면 될 것 같습니다~
댓글을 작성하려면 로그인해야 합니다.
gaelim 6년 전
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)]로 저장되어야하는거같습니다..
이럴땐 어떻게 해야할까요.?...