디시인사이드 갤러리

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

갤러리 본문 영역

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

프갤러(218.148) 2025.07.13 19:08:52
조회 199 추천 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 - -
AD 곧 휴가!! 홈캉스, 바캉스 SALE 운영자 25/07/21 - -
공지 프로그래밍 갤러리 이용 안내 [88] 운영자 20.09.28 45746 65
2874491 ❤✨☀⭐⚡☘⛩나님 시작합니당⛩☘⚡⭐☀✨❤ ♥팬티스타킹냥덩♥갤로그로 이동합니다. 15:13 0 0
2874490 프론트 개발자 클린코딩의 한계 [1] ㅇㅇ(211.235) 15:08 9 0
2874489 자 오늘 일 끝이다 아스카영원히사랑해갤로그로 이동합니다. 15:07 5 0
2874488 프로그래머의 가장 큰 미덕은 끈기라고 생각함 ㅆㅇㅆ찡갤로그로 이동합니다. 14:57 11 0
2874487 공부가 뇌를 똑똑하게 하는게 아니라 노화시키는듯 ㅇㅇ(211.235) 14:56 12 0
2874485 유라랑 ㅆㅇㅆ 햄들은 모해????? [8] 프갤러(1.235) 14:52 28 0
2874484 개발머리 없어서 전산직 이직함 [1] ㅇㅇ갤로그로 이동합니다. 14:43 21 0
2874483 방구가 들끓는다 [2] 개멍청한유라갤로그로 이동합니다. 14:09 29 0
2874482 진짜너무덥다 [2] 개멍청한유라갤로그로 이동합니다. 14:04 29 0
2874480 30분 뒤 생 어금니 뽑을 예정 [5] 발명도둑잡기(211.246) 13:51 29 0
2874479 전설의 로스트미디어 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 13:41 22 0
2874477 통장에 1억 있는 개새끼들은 봐라 [7] 아스카영원히사랑해갤로그로 이동합니다. 13:39 58 0
2874476 다들 뉴프로에 글남겨서 피드백받자 헬마스터갤로그로 이동합니다. 13:27 23 0
2874475 wix 로 사이트 제작중인데 팝업기능 어딨어? 헬프! 헬프!! 삑사리갤로그로 이동합니다. 13:19 24 0
2874474 제습기 사고 인생이 달라졌다 [5] 헬마스터갤로그로 이동합니다. 13:16 33 0
2874473 현실적인 비전공자 루트 프갤러(121.145) 13:12 43 0
2874472 성냥사세양..성냥사세양.. 성냥말구 다른것두 팔아양.. [1] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 13:11 22 0
2874471 프갤 망했다 [2] 프갤러(211.210) 13:03 39 0
2874470 좆소월급들어왔다. [9] 개멍청한유라갤로그로 이동합니다. 13:03 60 0
2874469 나님 회복 시나리오 돌리고 있는데 성공할지 모르겠음 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 12:56 16 0
2874468 개발자 취업,,, [3] 프갤러(210.126) 12:53 53 0
2874467 양키의 에반게리온 전체 요약 특촬물 ㅋㅋㅋ 프갤러(183.101) 12:34 20 0
2874466 아패로 윈도 돌리구 싶당 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 12:32 15 0
2874465 스마트폰 버튼 키 기능 할당 질문 [1] ㅇㅇ(14.35) 12:21 23 0
2874462 새 umpc 발명도둑잡기(118.235) 12:08 19 0
2874461 적금 붓고 주식 사니까 [7] 아스카영원히사랑해갤로그로 이동합니다. 12:04 73 0
2874460 월급 입갤!!!!!!!!!!!!!!!!! [1] 아스카영원히사랑해갤로그로 이동합니다. 11:56 52 0
2874459 CT 찍어야 하냐 자꾸 불운이 많지 .. 넥도리아(223.38) 11:53 14 0
2874458 만화방와서 올만에 만화보는데 [6] ㅆㅇㅆ찡갤로그로 이동합니다. 11:42 44 0
2874457 종북 매국노 반국가세력 간첩 [1] ♥팬티스타킹냥덩♥갤로그로 이동합니다. 11:39 29 0
2874455 나님 살아오면서 항상 느끼는게 산업의 발전은 생각보다 너무 느리다 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 11:11 21 0
2874454 노인들이 강서 킬러 성수형님을 살인마라고 싫어하는이유 뒷통수한방(1.213) 11:10 14 0
2874451 월급날이댱 ㅇㅂㅇ 어린이노무현갤로그로 이동합니다. 10:35 26 0
2874450 좌빨배급견 = 깜둥이 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 10:27 17 0
2874449 2찢명 구정물 1원도 안남기고 다 써버리자! ♥팬티스타킹냥덩♥갤로그로 이동합니다. 10:09 19 0
2874448 공수처 검찰청 경찰청 국제수사 과학수사 포랜식수사 기무사 국정원 존재이유 뒷통수한방(1.213) 09:49 16 1
2874447 최강의 냥덩 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 09:44 20 0
2874446 백번 양보해도 파이썬은 프로그래밍 언어로써는 절대 아닌듯. 프갤러(59.16) 09:42 28 0
2874445 오늘은 아스카의 월급날입니다 [1] 아스카영원히사랑해갤로그로 이동합니다. 09:38 59 0
2874443 까치 ㅇㅅㅇ 헤르 미온느갤로그로 이동합니다. 09:31 13 0
2874442 오늘 입고 온 옷에서 냄새난다 [4] 아스카영원히사랑해갤로그로 이동합니다. 09:29 39 0
2874441 고무백 30살인데 존나 노력하면 2800 si 가능? [1] 프갤러(106.101) 09:23 26 0
2874440 돈데 돈내 곤데 꼰대 똥내 ♥팬티스타킹냥덩♥갤로그로 이동합니다. 09:13 17 0
2874439 ❤✨☀⭐⚡☘⛩나님 시작합니당⛩☘⚡⭐☀✨❤ ♥팬티스타킹냥덩♥갤로그로 이동합니다. 09:12 14 0
2874436 태연 ㅇㅅㅇ 헤르 미온느갤로그로 이동합니다. 08:33 18 0
2874435 하루 한 번 헤르미온느 찬양 헤르 미온느갤로그로 이동합니다. 08:31 25 0
2874434 학점 3.4 ADHD좌 어디갔음? 프갤러(223.194) 08:06 24 0
2874428 PC, 스마트폰, 일정작성 영어로 전부 하면 도움되나요? 질문왕(211.198) 07:11 12 0
2874411 일본 관세 15프로 맞자고 지옥으로 갔노 [2] ㅆㅇㅆ찡갤로그로 이동합니다. 06:37 47 1
뉴스 여은, 오늘(24일) 새 싱글 ‘밤 하늘의 별도 너처럼 빛나진 않잖아’ 발매! 여름밤 울리는 감성 고백송! 디시트렌드 07.24
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

뉴스

디시미디어

디시이슈

1/2