■ 문제 개요

도형 공장을 만들려고 합니다.

도형은 여러 층으로 쌓여 있고, 각 층은 네 개의 사분면으로 나뉘어 있습니다.

우리는 정해진 몇 가지 조각 종류를 조합해서 목표 도형을 만들려고 합니다.

여기서 도형을 만들기 위한 기본 규칙과 가능한 연산들이 정해져 있고,

이걸 활용해서 최소한의 연산으로 목표 도형을 완성하는 게 문제입니다.

시작 도형은 1층에 S 조각 4개가 꽉 차 있는 "SSSS"입니다.

한번 만든 도형은 무한히 재사용할 수 있습니다.

■ 1. 도형 구조

도형은 최대 5층까지 쌓을 수 있습니다.

각 층은 4개의 사분면으로 나누어져 있고 원형 연결성이 있습니다.

사분면 번호는 다음과 같습니다.

[4 (TL)] [1 (TR)]

[3 (BL)] [2 (BR)]

즉, 하나의 도형은 5x4의 격자 구조로 이루어져 있습니다.

■ 2. 조각 종류

도형을 구성하는 조각은 다음 네 가지입니다.

기호 | 설명

S | 고체 조각

P | 핀 조각

c | 크리스탈 조각

- | 빈 공간

■ 3. 도형 표현 방법

도형은 문자열로 표현합니다.

각 층은 4글자이며, 각각 사분면 1(TR), 2(BR), 3(BL), 4(TL) 순서로 조각을 나타냅니다.

여러 층이 있을 경우 :로 층을 구분합니다.

예를 들어:

S--- → 1층에서 1사분면 위치에 S 조각, 나머지는 빈 공간

-S--:----:---S → 1층 2사분면에 S, 3층 4사분면에 S 조각이 있다는 뜻입니다.

뒤쪽의 ---- 는 생략 가능합니다.

빈 도형은 null 대신 ---- 로 표현합니다.

■ 4. 물리 규칙

조각들이 안정적으로 쌓여야 하며, 다음 규칙을 따릅니다.

4.1 연결성

S 조각은 같은 층 내에서 상하좌우로 인접한 조각끼리만 연결됩니다.

ex) 모두 연결됨 SS--, S--S (1사분면과 4 사분면은 원형으로 이어져있습니다.)

c 조각은 같은 층 내 상하좌우, 그리고 위아래 층 동일 사분면 조각과 연결됩니다.

크리스탈 c 는 연결성이 강하지만 연약하므로, 어떤 형태로든 파괴된다면 연결된 모든 크리스탈 또한 함께 파괴됩니다.

이 파괴의 충격은 c 연결 간에만 전달됩니다. S 연결을 통해 파괴의 충격이 전달되지는 않습니다.

ex) 모두 연결됨 -c--:ccc-:-c--

S 조각과 c 조각끼리는 같은 층 내에서 상하좌우로 인접한 조각끼리만 연결됩니다.

ex) 2층에서만 연결됨 -S---:ScS-

P 조각은 연결이 없습니다.

4.2 지지 조건

1층에 있는 조각은 항상 지지됩니다.

ex) S---

위층 조각은 바로 아래층 같은 사분면에 조각이 있어야 지지됩니다.

ex) 지지됨 S---:S---, 지지되지 않음 S---:-S--

같은 층 내에서 이미 지지된 S 조각과 연결되어 있으면 지지를 받을 수 있습니다.

ex) 지지됨 S---:SS--

연결된 조각들로 이루어진 그룹 내에 지지된 조각이 하나라도 있으면 그룹 전체가 지지됩니다.

ex) 지지됨 S---:SS--:-S--

4.3 중력 및 불안정 조각 처리

지지되지 않는 모든 도형은 중력에 의해 아래층으로 쭉 떨어집니다.

지지되지 않는 S와 P 조각은 그룹 단위로 아래층으로 쭉 떨어집니다.

ex) 사례1 S---:S---:-S--:-S-- → SS--:SS-- 3,4 층이 떨어질때, 중간에 2층에서 연결되지 않습니다.

사례2 S---:P---:----:SPSS → SP--:P---:S-SS

크리스탈 조각 c 는 연약합니다. c 가 중력에 의해 이동하거나, 절단에 의해 분리된 경우

해당 c 조각은 연결된 그룹 c 조각들과 함께 모두 파괴됩니다.

ex) 사례1 ----:--cc:--[...] --S-

사례2 cccc:----:cccc → cccc 두 크리스탈 그룹은 분리된 그룹임

이 과정을 안정될 때까지 반복합니다.

■ 5. 도형을 다루는 연산

아래 여섯 가지 연산으로만 도형을 가공할 수 있습니다.

5.1 회전 (rotate)

rotate(A: shape) -> shape

도형을 시계 방향으로 90도 회전합니다.

사분면 번호는 [1,2,3,4] → [4,1,2,3]로 바뀝니다.

예시)

rotate(PP--:-SS-) -> -PP-:--SS

5.2 적층 (stack)

stack(A: shape, B: shape) -> shape

A 도형 위에 B 도형을 쌓습니다.

B 도형의 c 조각은 쌓는 과정에서 중력에 의한 충격에 의해 모두 파괴됩니다.

두 도형을 쌓고, 5층을 초과하면 윗부분은 제거합니다.

다시 물리 적용합니다.

예시)

stack(SSSS:SS--, --SS:SSSS) -> SSSS:SSSS:SSSS

stack(cSSc, cccS) -> cSSc:---S 크리스탈 파괴

stack(SSSS:SSSS:SSSS, SSSS:SSSS:SSSS) -> SSSS:SSSS:SSSS:SSSS:SSSS 5층 초과 제거

stack(-SSS:-SSS:-SSS:-SSS:-SSS, PPPP:SSSS) -> PSSS:-SSS:-SSS:-SSS:-SSS (응용) 핀만 있는 레이어 제작 과정

5.3 절단 파괴 (destroy_half)

destroy_half(A: shape) -> shape

도형의 모든 층을 관통하도록 좌우 반으로 나눕니다.

좌측 도형 사분면 4(TL), 3(BL)을 파괴합니다.

우측 도형 사분면 1(TR), 2(BR)만 남깁니다.

다시 물리 적용합니다.

예시)

destroy_half(SSSS:SSSS) -> SS--:SS--

destroy_half(ScSc:ccSS) -> [...]--:cc--

destroy_half(ccSS:SccS) -> S--- 크리스탈 연쇄 파괴

destroy_half(PPPP:cccc) -> PP-- (응용) 핀만 있는 레이어 제작

destroy_half(cSSc:SSSS:cSSS) -> -S--:SS--:cS-- (응용) 1사분면에서 크리스탈 아래 공백 -[...]* 제작

destroy_half(S-S-:PSS-:ScS-) -> SS--:P---:[...]-- (응용) 2사분면에서 크리스탈 아래 공백 및 도형 낙하 S-c* 제작

*임의로 분류한 패턴명 입니다.

5.4 스왑 (swap)

swap(A: shape, B: shape) -> (shape, shape)

두 도형을 각각 절단(cut)해 좌우를 나눈 뒤, 물리 적용합니다.

A 도형의 우측과 B 도형의 좌측을 합쳐 새 도형을 만듭니다.

나머지 도형도 같은 방식으로 만듭니다.

각 새 도형에 물리 적용이 일어납니다.

예시)

swap(SSSS:SSSS,PPPP) -> (SSPP:SS--, PPSS:--SS)

swap(P---:S--S, P---:S--S) -> (P--S:S---, P--S:S---) 중력 적용

swap(SS--,--SS) -> (SSSS, ----)

swap(cc--:S--S, c--c:S--S) -> (cc-S:S---, S--S) 분리로 인한 크리스탈 파괴

5.5 핀 푸쉬 (pin_push)

pin_push(A: shape) -> shape

모든 도형을 1층씩 들어 올립니다.

1층에 기존 조각이 있는 위치마다 P 조각을 추가합니다.

만약 층이 5층을 초과했다면 윗부분은 파괴합니다.

이후 물리 적용합니다.

예시)

pin_push(SSSS) -> PPPP:SSSS

pin_push(-SPc:SSSS) -> -PPP:SPc:SSSS

pin_push([...]--:SSSS:cccc:c---:c---) -> PP--:[...]--:SSSS 층 초과로 인한 크리스탈 연쇄 파괴

pin_push(ccP-:cSP-:cSS-:c---:c---) -> PPP-:-SP-:--P-:-SS- 분리 원리

pin_push(cc--:cP--:cP--:cP--:cS--) -> PP--:-P--:-P--:-P-- 도형 파괴 원리

pin_push(ccc-:c-S-:c-c-:c---:c---) -> PPP-:--S- 세컨드 크리스탈 파괴

pin_push(cccc:cccc:cccc:cccc:cccc) -> PPPP (응용) 핀 레이어 제작

pin_push(c-P-:cScS:c---:c---:c---) -> P-P-:--P-:-ScS (응용) 집게발* 제작

pin_push(cccP:SPcS:cSc-:--c-:--c-) -> PPPP:-P-P:S--S:cS-- (응용) 핀 게이트* 제작

pin_push(ccSP:SccS:PScc:ScSc:---c) -> PPPP:-SSP:S--S:P---:ScS- (응용) 도형 게이트* 제작

pin_push(S-[...]:PScc:S-[...]:ScSc:---c) -> PSPP:S-S-:P-S-:S---:ScS- (응용) 드롭+게이트* 제작

*임의로 분류한 패턴명 입니다.

5.6 크리스탈 생성 (crystal_generator)

crystal_generator(A: shape) -> shape

도형의 몇 층이 최상층인지 검사합니다.

1층부터 그 최상층까지의 빈 공간(-)과 P 조각을 모두 c 조각으로 바꿉니다.

예시)

crystal_generator(SSSS) -> SSSS

crystal_generator(P-S-:SP--) -> ccSc:Sccc

crystal_generator(SPc-) -> Sccc

■ 6. 게임 규칙과 목표

시작 도형은 1층에 S 조각 4개가 꽉 차 있는 "SSSS"입니다.

한번 만든 도형은 무한히 재사용할 수 있습니다.

■ 7. 문제

문제 1. 도형 제작 가능 여부

is_craftable(target: str) -> bool

무작위 도형이 문자열 입력으로 들어올 때,

시작 도형과 위 연산들만 써서 목표 도형을 만들 수 있는지 판단하세요.

예시)

"SSSS" -> True

"----" -> True

"PPPP:SSSS:cccc" -> True

"----:SSSS" -> False

"S---:SSSS" -> True

"cPSP:ScSP" -> True

"S---:cccc" -> False

"-S--:PS--" -> False

고급 예시)

"cS--:-S--:cS--" -> False

"cS--:-S--:SS--:cS" -> False

"-S--:SS--:cS--" -> True

"SS--:-S--:cS--" -> True

"-S--:SS--:-S--:cS--" -> True

"PS--:-S--:SS--:-S--:cS--" -> True

"SS--:-S--:SS--:-S--:cS--" -> True

"P-PP:SSSS:P--P:PcS-:ScSS" -> True

"P-P-:--P-:-ScS" -> True

"-S--:-S--:-SS-:SScS" -> True

"PP--:PS--:S-SS:P---:ScS-" -> False

문제 2. 최적 제작 과정 (도전 과제)

craft_sequence(target: str) -> List[str]

무작위 제작 가능한 도형이 문자열 입력으로 들어올 때,

목표 도형을 만드는 최소 연산 순서를 문자열 리스트로 출력하세요.

도형의 출력은 문자열 표현 방법을 준수합니다.

정답이 여러 개일 수 있습니다.

예시)

입력: "SS--:SS--"

출력:

[

"stack(SSSS, SSSS) -> SSSS:SSSS",

"destroy_half(SSSS:SSSS) -> SS--:SS--"

]

입력: "cc--:cc--"

출력:

[

"stack(SSSS, SSSS) -> SSSS:SSSS",

"destroy_half(SSSS:SSSS) -> SS--:SS--",

"crystal_generator(SS--:SS--) -> SScc:SScc",

"rotate(SScc:SScc) - > SccS:SccS",

"rotate(SccS:SccS) - > ccSS:ccSS",

"destroy_half(ccSS:ccSS) -> cc--:cc--"

]

문제 3. 일반화 (도전 과제)

도형의 구조가 최대 5층, 4사분면인 구조를 넘어서

n층, m사분면 에서도 문제 1, 2가 동작하도록 일반화하시오. (0 < n <= 20, 0 < m <= 20)

■ 8. 참고 사항

이 모든 규칙과 연산은 Shapez2 게임의 룰을 기반으로 하며, 논리가 충돌할 경우 원작 게임의 규칙을 우선시 합니다.

연산의 입력중 하나라도 완전히 비어있다면 ---- 아무 동작도 하지 않습니다.

캐싱 및 룩업 테이블 등 모든 최적화 기법의 사용이 허용됩니다.

현재 문제는 정답이 완전히 확정되지 않았습니다.

글자수 제한때매 예시몇개랑 가독성 날림
한달동안 매달렸는데 감도못잡겠음 너무 복잡함 2,3 번 문제 무시하고 1번이라도 풀어주실분