[💬] 알고리즘 질문

[익명(128.134)]

소코반류 퍼즐 생각하고 있습니다

블럭은 테트리스처럼 여러모양입니다

주인공은 힘이 쎄서 한번에 여러 블럭을 밀 수 있습니다

기본적인 알고리즘은 아래와 같습니다

블럭을 밀면 그 블럭은 진행방향에 접해있는 다른 모든 블럭을 밀고 그 블럭들은 또 자기네들 진행방향에 있는 다른 모든 블럭을 밉니다

그래서 마지막 블럭까지 모두 진행방향에 벽이 없다면 다 밀립니다

하나라도 벽에 막힌다면 블럭들은 밀리지 않습니다

그림을 그려봤어요

이해가 되시나여?

근데 문제는 오목한 모양의 블럭입니다

오목한 구멍에 블럭이 존재하면 이게 주화입마에 빠집니다

아래 그림을 봐주세요

오목한 블럭을 밀면 진행방향에 접해있는 블럭을 미는데 그 블럭도 역시 진행방향에 있는 블럭을 밀게되고 그게 그 처음에 오목한 블럭이라서 또 아까 그 블럭을 또 밀게 되고...

그래서 이게 주화입마에 빠져서 스택이 폭발할 거 같습니다

어째야되나요?????????????????ㅠㅠ

[익명(39.118)]

기ㅚㄱ떠밥당ㅁ엔 알고맂ㅁ이냐 ㅋㅋ

[익명(128.134)]

기획자 떡밥아닙니다 겜스로 만들고에여

[익명(128.134)]

아 생각났다 스택에 새로운 블럭이 쌓일 때마다 스택에서 같은 블럭이 있나 찾아보고 있으면 그냥 안막혀있다고 판단해도 될 거 같네요 맞져?

[123(61.73)]

밀어야 하는 블럭을 계산해서 동시에 딱 한번 밀면 안되나요

[익명(222.119)]

1. 모든 블럭을 하나의 정사각형의 조합으로 나눈다. 예시) ㄱ 이면 정사각형이 3개 있는거임 2. 진행방향을 받는다. 왼오위아래 중 하나 3. 진행방향에 있는 각 블럭 중 붙어 있는 블럭을 포함하여 하나의 트리로 만든다. 5. 트리로 만드는 과정에서 빈 공간이 생기면 leaf 노드가 되는거임 6. 각 leaf 노드를 조사. leaf 노드에 장애물이 없을 경우 진행 방향으로 한칸 밀기 가능. (다만 주인공 바로 앞에 있는 leaf는 검사에서 제외한다.) 이해안가면 글하나 써서 만들어 줌

[익명(222.119)]

주인공 바로 앞에 있는 leaf노드란 건 depth가 1인 leaf노드를 말하는거임

[익명(222.119)]

아 굳이 트리로 만들 필요가 없고 각 줄만 한번씩 싹 비교 하고 빈 타일 나오면 동적 행렬에 depth랑 노드 포인터만 넣어두면 될듯

[익명(118.47)]

접촉한 모든 블럭을 하나로 묶은 다음에 (지금 처럼 바로 밀지 말고 임시 리스트에만 추가. 중복 제거) 묶인 블럭을 타일에서 모두 제거 묶인 블럭을 한칸 이동한 위치에 타일 들이 모두 비어 있는지 검사. 비어 있으면 묶인 블럭을 재배치.

[익명(128.134)]

오 다들 감사합니다 띠용띠용