디시인사이드 갤러리

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

갤러리 본문 영역

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

프갤러(218.148) 2025.07.13 19:08:52
조회 201 추천 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/07/21 - -
공지 프로그래밍 갤러리 이용 안내 [88] 운영자 20.09.28 45786 65
2875093 '1 9 ) 윤공주 벗 방한대 ㄱㄱ 프갤러(203.251) 04:11 0 0
2875091 앱히키 그 존마니가 추천한 인강 기억나시는 분?? 프갤러(222.108) 04:09 1 0
2875090 신태일 틱톡에서 실시간 떡방중이네 ㅋㅋㅋ 프갤러(203.251) 04:08 2 0
2875083 여사친 섹트 박제됨ㅋㅋ 파치카갤로그로 이동합니다. 03:54 9 0
2875076 민생지원금 뿌리는게 물가상승이랑 상관없는 이유 (팩트체크) [2] 야옹아저씨갤로그로 이동합니다. 02:42 26 0
2875064 재벌해체가 답인 이유 [5] 야옹아저씨갤로그로 이동합니다. 01:54 65 7
2875063 음기 충전 발명도둑잡기(118.216) 01:46 15 0
2875056 와 나 순간 await 문법 여는법이 안 떠올라서 헤맸다 [2] ㅆㅇㅆ(124.216) 01:25 35 0
2875053 역성혁명 발명도둑잡기(39.7) 01:16 11 0
2875049 “리박스쿨은 빙산의 일각…‘밈 전쟁’에서 놀이가 된 혐오 발명도둑잡기(39.7) 01:06 14 0
2875048 홍준표 "신천지 10만 명 국힘 입당…교주가 尹 돕는다더라" 발명도둑잡기(39.7) 01:01 13 0
2875047 여사친 섹트찾았는데 어캄? 헤치갤로그로 이동합니다. 00:53 26 0
2875044 1978년 7월 서울 남산동에서 무더운 여름 밤이계속되자 발명도둑잡기(39.7) 00:33 16 0
2875043 일본에서 실제로 일어난 사건 발명도둑잡기(39.7) 00:31 22 0
2875041 40도가 넘는 천막에서 민주노총과 진보당은 발명도둑잡기(39.7) 00:30 14 0
2875040 C #은 마이크로소프트 소속언어인데 왜이렇개 병신같을까 뒷통수한방(1.213) 00:24 25 0
2875038 공수처 검찰청 경찰청 국제수사 과학수사 포랜식수사 기무사 국정원 존재이유 뒷통수한방(1.213) 00:14 11 0
2875037 전기 모기채 발명한 사람이 번 돈 발명도둑잡기(39.7) 00:14 20 0
2875034 지잡대 컴공 한국나이 28살 졸업이면 많이 늦은거냐 [1] 프갤러(119.193) 07.26 48 0
2875033 에반게리온 구극장판에서 달콤한죽음대신 이노래 어떰? ㅇㅇ(183.101) 07.26 24 0
2875031 사도마조히즘 노예들 해방 중 발명도둑잡기(39.7) 07.26 18 0
2875029 오늘의 소설, 영화 실마리: 모기 유전자조작으로 전염병을 퍼뜨리며 전쟁 발명도둑잡기(118.216) 07.26 18 0
2875025 아 ㅅㅂ 자려는데 모기잇는듯 개빡치넹 [1] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 07.26 35 0
2875023 갑부 칸예도 파이럿베이에서 가상악기 불법 다운로드 발명도둑잡기(118.216) 07.26 16 0
2875022 '후방 ) 권은비 일본 공연 중 꼭노 프갤러(58.224) 07.26 32 0
2875020 '후방 ) 권은비 일본 공연 중 꼭노 프갤러(58.224) 07.26 24 0
2875018 칸예 나치 관련 이상한 점 [1] 발명도둑잡기(118.216) 07.26 28 0
2875017 언어 한번 만들어보고 싶지 않냐 [5] ㅆㅇㅆ(124.216) 07.26 61 0
2875016 C# 최대 단점, FreeBSD에서 사용하기 뭐 같음 나르시갤로그로 이동합니다. 07.26 25 0
2875015 백악관 개빡돌게 만든 사우스파크 에피소드 발명도둑잡기(118.216) 07.26 17 0
2875011 ❤✨☀⭐⚡☘⛩나님 탈갤합니당⛩☘⚡⭐☀✨❤ [1] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 07.26 29 0
2875008 프갤 또 뉴스탈듯.. 운명은 바꿀수 없는걸깡.. [2] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 07.26 42 0
2875004 C# 진짜 해보면 만족도가 너무 높긴함 [2] ㅆㅇㅆ(124.216) 07.26 55 0
2875003 성냥사세양..성냥사세양.. 성냥말구 다른것두 팔아양.. [4] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 07.26 40 0
2875002 C#에 절여져서 다른 언어를 못하겠다 [4] 루도그담당(58.239) 07.26 57 0
2874999 군대에서 프로그래밍 공부하는법 [3] 프갤러(58.232) 07.26 52 0
2874997 "폭염때문에 너무 뜨거워 마트서 사온 '오리 알'이 부화했어요" 발명도둑잡기(39.7) 07.26 18 0
2874995 커피를 마시며 명상을 하려고 합니다 [15] 아스카영원히사랑해갤로그로 이동합니다. 07.26 75 0
2874993 나님 제 2의 원종이가 나오지 않도록 멍유 케어해주고 있는데.. 뭔가.. [9] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 07.26 51 0
2874991 아스카영원히사랑해씨 출입증 나왔습니다 [13] 헬마스터갤로그로 이동합니다. 07.26 59 2
2874989 sap ui5 개좆같다 ㄹㅇ [2] ㅇㅇ(39.7) 07.26 27 0
2874988 저는 크몽, 숨은 고수에서 5만원에 소통과 이야기 할 수 있습니다. [4] ㅆㅇㅆ(124.216) 07.26 52 0
2874986 베르세르크 작가의 생애. ㅇㅇ(183.101) 07.26 25 0
2874984 ㅆㅇㅆ과 진지한 대화를 하고 싶다 [3] 아스카영원히사랑해갤로그로 이동합니다. 07.26 52 0
2874983 뉴프로 전환율을 높이기 위해 비회원 댓글창을 표시하다 헬마스터갤로그로 이동합니다. 07.26 23 0
2874982 요즘 인싸들 진격거보고 꺼드럭거리는거 개빡침 [4] 어린이노무현갤로그로 이동합니다. 07.26 58 2
2874981 원종이 IQ 높았냐? [4] ㅇㅇ(211.234) 07.26 46 0
2874980 누가 나님 냥덩이 만진거야? [5] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 07.26 40 0
2874978 흔한 화상회의 ㅇㅇ(183.101) 07.26 20 0
뉴스 '한끼합쇼' 김희선X탁재훈, 띵동 성공을 위한 애교 폭격+집 청소 특급 서비스 개시! 은평구 한옥마을서 16분 남기고 밥 친구 찾기 성공! 디시트렌드 07.25
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2