조합가능한 모양수를 구하는 알고리즘
찬누리
2023.04.01
질문 제목 : ㅁ박스 개수별로 만들 수 있는 모양의 총개수
네모박스 n개 있을떄 테트리스 블럭처럼 박스를 이용 해서 만들 수 있는 모양의 총 개수 구하는 알고리즘 구상질문 내용 :네모박스 갯수를 4개 5개 6개... 이렇게 바꿔가면서 테트리스 블럭모양처럼 네모박스로 만들 수 있는 모양의 개수를 알 수 있는 알고리즘을 만들려고합니다. 회전 해서 같은모양은 하나로 인정하구요 제가 생각한게 n*n 배열 만들어서 백트래킹으로 모든 경우 체크해서 모양 완성되는건 새로운 배열에 넣어놓고 모양이 만들어 질 때 마다 기존에 만들어진 블럭들을 가로세로 움직여서 중복 체크 하려고 했는데 도저히 회전은 어떻게 배제해야될지 모르겠네요 ㅠㅠ 좋은 아이디어가 있을까요
혹은 제가 생각한 방법말고 더 신박한거 있을가요
(예를 들면 ㅁ 4개로 만들 수 있는 모양의 총개수는 7개)
-
큰힘
감사합니다 덕분에 해결했어요!!
-
퐁당
문제가 재미있네요.
one-sided polyominoes 를 검색해보세요. -
오미자
수식은 직접 계산 하셔야죠,, 어쩔수가 없어요,, ㅠㅠ
-
누림
어떤 수식 말씀 하시는건가요 그래도 수식을써도 백트래킹은 불가피 한거 아닌가요 ㅠㅠ? 수식에 부합한지 안한지 확인하려면 일일이..
-
by풀잎
근데 이런걸 다 체크하기엔 너무 많은 양을 검사하는거같아요..
4*4 배열만 생각해도 끔찍한데,,,
차라리 수식을 찾아보는게 더 빠를꺼같아요