디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

한달동안 매달려도 못푼 알고리즘문제 풀어줄사람ㅜㅜ

프갤러(218.148) 2025.07.13 19:08:52
조회 242 추천 0 댓글 16
														

■ 문제 개요

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

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

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

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

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

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

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

■ 1. 도형 구조

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

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

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

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

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

7ded8168f5dc3f8650bbd58b3684716dd260



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

7ded8268f5dc3f8650bbd58b36897d68a8a9



■ 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:--Sc → --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) -> Sc--:cc--

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

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

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

destroy_half(S-S-:PSS-:ScS-) -> SS--:P---:Sc-- (응용) 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(Sc--:SSSS:cccc:c---:c---) -> PP--:Sc--: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-Sc:PScc:S-Sc: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--"

]

7ded8368f5dc3f8650bbd58b368277686926


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

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

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

■ 8. 참고 사항

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

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

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

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



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

추천 비추천

0

고정닉 0

0

댓글 영역

전체 댓글 0
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 해외에서 겪는 불합리한 대우에 대응 잘 할 것 같은 스타는? 운영자 25/11/03 - -
AD 저녁 뭐먹지? 오늘의 메뉴 추천! 운영자 25/10/31 - -
2872958 헤롱헤롱 발명도둑잡기갤로그로 이동합니다. 07.19 68 0
2872956 엄마가 내 방 쓰레기래... 랜다. 낮에 [7] 넥도리아(220.74) 07.19 113 0
2872955 첨왔는데 프로그래밍 갤러리에 념글이 왜케 정치적인글이 많음? [3] 프갤러(121.151) 07.19 116 0
2872953 나 차단당했냐? 19금 올려서.... [1] 넥도리아(220.74) 07.19 96 0
2872950 ❤✨☀⭐⚡☘♥+나님 시작합니당♥+☘⚡⭐☀✨❤ ♥삣삐냥덩♥갤로그로 이동합니다. 07.19 86 0
2872949 2년차 신입 초보 웹개발자인데 이 책들 공부할까요 (+선배님들의 조언부탁 [4] 프갤러(112.133) 07.19 199 0
2872948 형님들 전자과인데 [3] 단팥빵갤로그로 이동합니다. 07.19 135 0
2872947 나님 오늘의 미션을 완수하고 복귀하시다. [2] 헬마에스트로(211.235) 07.19 121 0
2872946 친중 2찢명 때문에 이제 자동차사고 존나 많이날듯 ♥삣삐냥덩♥갤로그로 이동합니다. 07.19 114 0
2872945 어케 멍퀴벌레는 24시간 일주일 내내 발정 나있는걸깡? [8] ♥삣삐냥덩♥갤로그로 이동합니다. 07.19 137 0
2872944 핸드폰 중고로 사려는데 XZ1 순정롬 넥도리아(220.74) 07.19 71 0
2872943 내 친구 강유현이 그립구나 [5] ㅆㅇㅆ(124.216) 07.19 129 0
2872942 에구구 이눔아! ♥삣삐냥덩♥갤로그로 이동합니다. 07.19 79 0
2872940 잡아먹힐거 같아.. [5] ♥삣삐냥덩♥갤로그로 이동합니다. 07.19 113 0
2872939 C++ Malloc 쓴다는 병신 들어와라 프갤러(106.101) 07.19 124 1
2872937 옛날 프갤은 언제를 말하는건가요? [11] 개멍청한유라갤로그로 이동합니다. 07.19 173 0
2872936 옛날프갤이 그립당.. [3] ♥삣삐냥덩♥갤로그로 이동합니다. 07.19 114 0
2872935 옛사람들 나이를 생각해보면 왜 안오는지 대충 짐작이 가지 [3] 프갤러(110.8) 07.19 138 0
2872932 ㅇㅅㅇ❤+ ♥냥덩이는충전중♥갤로그로 이동합니다. 07.19 75 0
2872931 ㅔ근데 요즘 퓨어 c++ 쓰는사람 없어서 malloc 모를수있다봄 [3] 초코냥갤로그로 이동합니다. 07.19 163 0
2872930 전세계 부정선거조작 배후 밝혀졌넹 ㄷㅅㄷ ♥냥덩이는충전중♥갤로그로 이동합니다. 07.19 89 0
2872929 옛날사람들 왜 안옴? 배구공(119.202) 07.19 75 0
2872928 구멍 ♥냥덩이는충전중♥갤로그로 이동합니다. 07.19 76 0
2872927 new malloc 지랄하지 말고 러스트 써라 [3] 프갤러(211.234) 07.19 132 0
2872925 모기 있는거 같아서 찜찜하당.. ♥냥덩이는충전중♥갤로그로 이동합니다. 07.19 90 0
2872923 진정한 개발자들로 다시 프로그래밍 갤러리 살려야함 [1] 초코냥갤로그로 이동합니다. 07.19 140 0
2872922 이제 나이들어서 [1] 배구공(119.202) 07.19 108 0
2872921 가끔은 과거 프갤이 그립다 ㅇㅅㅇ.. [1] 초코냥갤로그로 이동합니다. 07.19 157 0
2872917 경상도 분들이 많으신듯 배구공(119.202) 07.19 97 0
2872916 과학교육과 여신 발명도둑잡기갤로그로 이동합니다. 07.19 67 0
2872915 난 그래도 ㅆㅇㅆ리스펙한다 [1] 초코냥갤로그로 이동합니다. 07.19 127 0
2872913 사람들이 왜 차타는지 알거같아요 개멍청한유라갤로그로 이동합니다. 07.19 92 0
2872911 징글징글하다 [9] 개멍청한유라갤로그로 이동합니다. 07.19 120 0
2872907 형들 34살 취업 조언점 [10] 프갤러(116.39) 07.19 528 0
2872905 OEM 잠금해제가 어떤지 없더라고, 넥도리아(220.74) 07.19 80 0
2872903 SD카드인데... 흠나... 넥도리아(220.74) 07.19 76 0
2872901 요즘 시대에 영어 공부가 꼭 필요할까요? [1] 질문왕(121.171) 07.19 95 0
2872900 강박증 심하면 언어 갈수록 흩트러지는 거 스트레쓰 받겠지 [3] 발명도둑잡기갤로그로 이동합니다. 07.19 101 0
2872898 네이버 AI가 왜 깔아져 있지? [2] 넥도리아(220.74) 07.19 109 0
2872897 이재명 대통령님께 당부드리는 흡연자 저격 아버지 포함 전자담배 빼고, 넥도리아(220.74) 07.19 253 0
2872896 애초에 수치 계산할때 malloc쓰라는 이유가 연속 메모리할당 [10] ㅆㅇㅆ(124.216) 07.19 148 1
2872895 ❤✨☀⭐⚡☘♥+나님 시작합니당♥+☘⚡⭐☀✨❤ [2] ♥냥덩이는충전중♥갤로그로 이동합니다. 07.19 96 0
2872894 결국 빤스런했노 ㅋㅋ 애초에 내가 씨발 초전도체 물성 계산한다고 CPP [3] ㅆㅇㅆ(124.216) 07.19 127 0
2872892 고수준에서만 작업하는 애들은 [8] 루도그담당(118.235) 07.19 184 0
2872891 애초에 ecs지피티한테 짜달라하면 맵기반으로 ㅆㅇㅆ찡갤로그로 이동합니다. 07.19 91 0
2872889 현업들한테 질문 [2] 프갤러(49.169) 07.19 124 0
2872888 요즘은 지가 쳐모른다고 지피티 운운하는 새끼들 개패고싶네 [4] ㅆㅇㅆ찡갤로그로 이동합니다. 07.19 112 0
2872887 지가 모른다고 지피티ㅋㅋ 저새낀 병신인가 ㅆㅇㅆ찡갤로그로 이동합니다. 07.19 72 0
2872884 CPP에서 malloc 쓰지말란건 일반적으로 고수준 에서 쓰지말란거지 [6] ㅆㅇㅆ(124.216) 07.19 162 0
2872883 웹 개발 커미션 받는데 별의 별 사람이 다 있음 [2] ㅇㅇ갤로그로 이동합니다. 07.19 127 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

디시미디어

디시이슈

1/2