디시인사이드 갤러리

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

갤러리 본문 영역

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

프갤러(218.148) 2025.07.13 19:08:52
조회 226 추천 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/10/06 - -
AD 프로게이머가 될테야!! 운영자 25/10/01 - -
공지 프로그래밍 갤러리 이용 안내 [96] 운영자 20.09.28 47849 65
2895585 출산율 여러가지 의미하자 혼외자 등등 공정거래위원회 넥도리나(220.74) 06:36 10 0
2895584 오늘자 남기는 데이터 복구 사진 최상묵 경제 전 부총리 기획재정부 넥도리나(220.74) 06:30 11 0
2895583 03 이대남 이잼 지지 인증합니다. 칸예갤로그로 이동합니다. 05:32 17 0
2895582 내가 종종 앱히키를 욕하는 이유 [2] 프갤러(39.7) 05:00 49 0
2895581 행님들 좋은아침입니다. 코딩 입문하고 싶읍니다. [2] 프갤러(180.66) 04:53 40 0
2895580 앱히키 씨발년은 하루에 한번씩 욕 처먹어야 한다. ㅇㅇ(222.108) 04:51 25 0
2895579 자문자답 존나 소름 돋네 [2] ㅇㅇ(124.48) 04:10 56 0
2895573 스팸에 김치볶음 이쁘게 담아봤다... 술안주로 먹을게 이것뿐이라... [1] ㅇㅇ(223.38) 02:30 27 0
2895569 이직준비 어케하냐고 100만번 물었다 [5] 밀우갤로그로 이동합니다. 01:38 61 0
2895565 슬슬 납품준비 끝났으니 자고 나머지 ㅆㅇㅆ(124.216) 00:52 27 0
2895563 캐시카우만 좀 안정되면 게임 계속 [2] ㅆㅇㅆ(124.216) 00:48 54 0
2895562 use client를 쓸때 단순하게 원칙만 정해두면 난 어렵지 않았음 [2] ㅆㅇㅆ(124.216) 00:36 46 0
2895561 개인적으로 나는 클라 출신이라 앱라우팅이 훨 편했음 [2] ㅆㅇㅆ(124.216) 00:32 47 0
2895560 리액트를 해야하나 말아야하나 존나 고민이다 [17] 프갤러(59.26) 00:23 161 0
2895558 이번 의뢰가 인문학계열에서 AI 도입하는데 이 과정에서 [2] ㅆㅇㅆ(124.216) 10.11 55 0
2895557 이번에 잘하면 진짜 연구 용역 될지도 모르겠다 [6] ㅆㅇㅆ(124.216) 10.11 98 1
2895556 강남 인기장소사이트 인기사이트(118.235) 10.11 35 0
2895555 중국하는 중국 chironpractor갤로그로 이동합니다. 10.11 27 0
2895552 업워크 일 3번 받았는데, 업워크쪽은 네이티브 잉글리쉬불가능이면 안받음 ㅆㅇㅆ(124.216) 10.11 33 0
2895550 아까 프리랜서 물어본 프붕인데 [7] 프갤러(218.153) 10.11 90 0
2895548 계미년에 태어나 살아오며 후회가 참 많다... ㅇㅇ(223.38) 10.11 19 0
2895547 저장용 ♥덩냥이♥갤로그로 이동합니다. 10.11 41 0
2895546 뉴프로가 프갤 먹었다고 함 헬마스터갤로그로 이동합니다. 10.11 38 0
2895545 여긴 도대체 왜 프로그래밍 관련 글이 없음? [2] 프갤러(159.196) 10.11 60 0
2895544 11월초..중순까지 밀릴듯? ♥덩냥이♥갤로그로 이동합니다. 10.11 36 0
2895541 ❤+ 없는 SEX는 공허하단걸 알아야행 [1] ♥덩냥이♥갤로그로 이동합니다. 10.11 38 0
2895540 컴퓨터 잘알 형들 질문점요 [2] ㅇㅇ(106.102) 10.11 37 0
2895539 민폐극좌 영포티는 인간으로 봐주는게 이상한것임 ♥덩냥이♥갤로그로 이동합니다. 10.11 22 0
2895538 [르몽드 살롱] 토마 피게티의 자유 무역 반대론 발명도둑잡기(118.235) 10.11 18 0
2895537 재매이햄 지지자 특징 [1] hrin(118.235) 10.11 40 0
2895536 스웨디시 아다땐 후기 ㅇㅇ(39.7) 10.11 53 0
2895535 이제 슬슬 공기 건조해지는듯? ♥덩냥이♥갤로그로 이동합니다. 10.11 35 0
2895533 음기 충전 발명도둑잡기(118.235) 10.11 39 0
2895531 안 잡아가요? 발명도둑잡기(118.235) 10.11 24 0
2895530 나님 왤케 뽀짝한걸깡? ♥덩냥이♥갤로그로 이동합니다. 10.11 40 0
2895529 트럼프 대통령에 영광 헌정 발명도둑잡기(118.235) 10.11 18 0
2895527 일베 서버 근황 발명도둑잡기(118.235) 10.11 54 0
2895526 ❤✨☀⭐⚡☘⛩수고했어양⛩☘⚡⭐☀✨❤ ♥덩냥이♥갤로그로 이동합니다. 10.11 45 0
2895524 쿠팡이츠 편의점 재고 실시간 업데이트 안됨? ㅇㅅㅇ 프갤러(112.157) 10.11 29 0
2895523 야 너두 버거킹 먹을 수 있어 프갤러(211.234) 10.11 34 0
2895521 이재명 말 안듣는 검사는 싹다 물갈이 해야 맞지 [9] 야옹아저씨갤로그로 이동합니다. 10.11 53 1
2895520 이거다 이거 [2] 발명도둑잡기(118.235) 10.11 51 0
2895517 자신의 존재 의의를 질의응답에서 찾아서 [2] 프갤러(211.235) 10.11 68 0
2895516 경력쫌 되면 위시캣이 제일 안전하고 돈 많이 받는다고 들음 [2] ㅆㅇㅆ(124.216) 10.11 69 0
2895511 프리랜서로 일해보고 싶은데 [4] 프갤러(218.153) 10.11 76 0
2895510 내가 석사수료로 대학원 중퇴한 이유 [1] 프갤러(211.235) 10.11 85 0
2895507 저녁은 버거킹이다. [3] 프갤러(223.63) 10.11 52 0
2895504 ㅆㅇㅆ야 난 네가 걱정돼서 하는 소리인데 ㅇㅇ(124.48) 10.11 80 5
2895502 완전 외부인이 본 모습 [3] 프갤러(175.116) 10.11 61 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

디시미디어

디시이슈

1/2