BOJ 18826 A+B (MC) - 2

우선 1편을 보고 오자 https://cookiehcl.tistory.com/5

BOJ 18826 A+B (MC)

백준이 섭종하는김에 A+B (MC) 숏코딩같은 이상한 짓을 하는 사람이 더 있나 살펴봤다.

하지만 열심히 쓴 글이 무색하게 6년이 넘는 시간동안 숏코딩을 시도해서 성공한 사람은 단 한명밖에 없었다....

 

그러다 문득 든 의문점. 1 chunk 이내로 코드를 만들면 2등 기록처럼 12288B로 제출할 수 있지만, 대 AI 딸깍 LLM 치팅시대라면 채점코드를 분석해서 더 줄일 수 있지 않을까?

 

대충 Gemini Pro한테 하루종일 상담받아본 결과 내린 결론은 다음과 같다.

- 사실 mca 파일 안에는 수많은 쓰레기 정보들이 들어있다. (빛 정보, 마인크래프트 맵 버전, 마을 생성여부 등등)

- 채점코드 분석 결과 Sections/Palette, Sections/BlockStates, Sections/Y, xPos, zPos를 제외한 모든 NBT를 지워도 된다고 한다.

- Sections 안에 Palette 없이 Y만 있는 공간은 air로만 가득찬 공간이므로 지워도 된다.

우선 NBTExplorer를 다운받아서 mca 파일을 뜯어본다.

기존에 있었던 수많은 NBT 정보들을

아래처럼 깔끔하게 바꿔준다.

 

이렇게만 하면........ 사실 크기가 안 줄어든다.

대체 메타데이터를 싹다 날렸는데 왜 크기가 안 줄어드냐? 다시 한번 Gemini 딸~깍을 해본다.

 

사실 mca파일은 무조건 4KB 단위로 섹터를 쪼개서 관리하는데,

• 오프셋 헤더 (청크가 어딨는지 확인하는 용도)
• 타임스탬프 헤더 (청크의 마지막 수정시간을 기록하는 용도)
• 청크 데이터 섹터 (실제 청크 데이터)

가 반드시 포함되어야 하기 때문에 12KB를 먹는다고 한다.

 

그런데 사실

1. 채점코드에서는 타임스탬프 헤더를 읽지 않는다.

2. 채점코드에서는 청크 데이터를 4KB를 그대로 읽는게 아니라 정확하게 청크 데이터의 크기만큼 읽는다.

 

그래서 이제 바이너리를 수정해서

• 타임스탬프 헤더를 지우고,
• 청크 데이터 섹터를 4KB 대신 정확하게 청크 데이터만큼만 남기고,
• 오프셋 헤더를 수정해서 4KB만큼 옮겨진 청크 데이터 섹터를 제대로 가르키도록 수정하면

진짜 파일 크기를 줄일 수 있다!!!

 

ImHex (마찬가지로 Gemini 추천작) 같은 헥스 에디터를 깐 다음,

• 타임스탬프 헤더를 지우고 (0x1000부터 0x1FFF까지 삭제)
• 청크 데이터 크기를 구한 뒤 (첫 4바이트가 청크 크기임, 5번째 바이트에 02가 오는게 정상사양)
  5번째 바이트부터 청크 크기만큼만 남기고 나머지를 전부 삭제한다. (즉, 0x1000부터 세면 청크 크기 + 4만큼만 남기기)
• 그 후 오프셋 헤더를 수정해서, 첫 3 바이트를 0x000001로 바꾼다. (원래 두번째 섹션부터 청크가 있다는 의미로 0x000002였을거임)

이렇게 하면 12KB 파일을 5074B로 줄일 수 있다!!

 

여기서 추가로 채점코드(+마인크래프트)는 mca 파일을 zlib를 사용해서 압축/해제하는데,

Gemini가 마인크래프트의 기본 압축과정인 zlib의 deflate보다 훨씬 효과적인 zopfli을 사용하면 청크 크기 자체를 줄일 수 있다고 한다.

zlib이 뭐 유명한 라이브러리라도 되는지 정말 우리한테 딱 필요한 "zlib의 inflate로 압축이 풀리지만 zlib보다 압축률 자체는 더 높은 라이브러리"를 구글에서 만들어줬다고 한다.

.... 솔직히 이쯤 됐으면 느꼈겠지만 백준 섭종할만했다. LLM이 너무 똑똑해졌다...

 

아무튼 zopfli까지 적용시키고 내친김에 헥스 에디터로 하던 작업도 싹다 해주는 파이썬 코드를 짜기로 했다.

마침 zopfli을 파이썬에서 쓰게 해주는 port도 존재해서 정말 딸깍으로만 코드를 짤 수 있었다.

 

뭐 어차피 LLM 치팅유저 됐는데(?) 주석 걍 AI가 내뱉은 그대로 달겠다.

import struct
import zlib
import zopfli.zlib


def full_optimize_mca(input_filename, output_filename):
    print(f"[*] '{input_filename}' 읽는 중...")
    with open(input_filename, "rb") as f:
        file_data = f.read()

    # 쾌감을 위한 원본 파일 크기 저장
    orig_file_size = len(file_data)

    # 1. 원본 파일에서 청크 오프셋 읽기 (파일의 가장 첫 3바이트)
    orig_offset_sector = (file_data[0] << 16) | (file_data[1] << 8) | file_data[2]
    orig_offset_bytes = orig_offset_sector * 4096

    if orig_offset_sector == 0:
        raise ValueError("에러: 청크 데이터가 존재하지 않거나 오프셋이 0입니다.")

    print(
        f"[*] 원본 청크 데이터 위치 감지: {orig_offset_sector} 섹터 ({hex(orig_offset_bytes)})"
    )

    # 2. 4KB 헤더 복사 및 오프셋 강제 변조 (헥스 에디팅 자동화)
    # 0x02(Sector 2)로 되어 있던 오프셋을 0x01(Sector 1)로 덮어씁니다.
    header = bytearray(file_data[:4096])
    header[0] = 0x00
    header[1] = 0x00
    header[2] = 0x01

    # 3. 변조하기 전의 "진짜" 원본 위치에서 청크 길이(sz)와 타입(02) 읽기
    sz_bytes = file_data[orig_offset_bytes : orig_offset_bytes + 4]
    sz = struct.unpack(">I", sz_bytes)[0]
    comp_type = file_data[orig_offset_bytes + 4]
    print(f"[*] 원본 청크 데이터 크기: {sz} bytes")

    if comp_type != 2:
        raise ValueError(
            f"에러: 지원하지 않는 압축 타입입니다 ({comp_type}). zlib(02)만 지원합니다."
        )

    # 4. 기존 zlib 페이로드 추출 및 압축 해제 (원본 NBT 확보)
    zlib_payload = file_data[orig_offset_bytes + 5 : orig_offset_bytes + 4 + sz]
    raw_nbt = zlib.decompress(zlib_payload)
    print(f"[*] 기존 압축 데이터 크기: {len(zlib_payload):,} bytes")

    # 5. Zopfli 극한 압축 시작
    print("\n[*] Zopfli 극한 압축 시작... ⚙️")
    zopfli_payload = zopfli.zlib.compress(raw_nbt)
    print("[*] 압축 완료!")

    # 6. 새로운 sz 계산 및 빅엔디안 패킹
    new_sz = len(zopfli_payload) + 1
    new_sz_bytes = struct.pack(">I", new_sz)
    print(f"[*] 새로운 청크 데이터 크기: {new_sz} bytes")

    # 7. 파일 작성 (타임스탬프 0x1000~0x1FFF 및 뒤쪽 패딩 찌꺼기는 쓰지 않고 자연스럽게 증발시킴)
    with open(output_filename, "wb") as f:
        f.write(header)  # 0x0000 ~ 0x0FFF (수정된 1섹터 가리키는 헤더)
        f.write(new_sz_bytes)  # 0x1000 ~ 0x1003 (새로운 크기)
        f.write(bytes([2]))  # 0x1004 (zlib 타입)
        f.write(zopfli_payload)  # 0x1005 ~ 파일 끝 (Zopfli 데이터)

    # 8. 대망의 결과 출력 (도파민 분비용)
    final_file_size = 4096 + 4 + 1 + len(zopfli_payload)
    saved_bytes = orig_file_size - final_file_size
    reduction_percent = (saved_bytes / orig_file_size) * 100

    print(f"\n[+] Hex 에디팅 & 패딩 절단 & Zopfli 최적화가 한 방에 완료되었습니다!")
    print(f"    - 원본 파일 크기: {orig_file_size:,} bytes")
    print(f"    - 최종 파일 크기: {final_file_size:,} bytes")
    print(f"    ==================================================")
    print(
        f"    🔥 총 {saved_bytes:,} bytes 증발! ({reduction_percent:.2f}% 용량 감소) 🎉"
    )
    print(f"    ==================================================")
    print(f"    - 결과물이 '{output_filename}' 에 저장되었습니다.")


if __name__ == "__main__":
    # 원본 파일명과 출력 파일명 세팅
    full_optimize_mca("r.0.0.mca", "r.0.0.optimized.mca")

 

이 모든 과정을 거치면 마침내 5036B라는 코드를 얻을 수 있게 된다.

 

하지만 백준이 섭종하는데 겨우 여기서 멈출것인가?

그렇다. 결국엔 이 "청크" 자체를 고쳐야만 여기서 더 숏코딩을 할 수 있다.

마인크래프트를 다시 깔아야 할 시간이다.

 

우선 마인크래프트 청크 구조에 대해 자세히 알아보자. (물론 Gemini 딸깍으로 얻은 정보라 교차검증은 안 해봤음)

• 청크 자체는 X,Z를 16단위로 나누고, 그 안에 있는 Sections는 Y를 16단위로 나눈다.
  즉 여기서 Y:0 부분은 Y=0~15, Y:1 부분은 Y=16~31이다.
• BlockStates는 각 Section의 어느 위치에 어떤 Palette 블록이 있는지 나열한거다.
• Palette는 각 Section마다 존재하는 블록들을 나열한거다.
  여기엔 air, sandstone, *_concrete 등도 포함되지만, 제일 중요한 redstone_wire, repeater 등의 경우 "Properties"를 가진다.
  Properties가 뭔 소리냐면 리피터의 경우 방향, delay, 레드스톤의 경우 동서남북에 연결된 레드스톤 여부, 파워 등등의 정보들을 의미한다. 즉 같은 레드스톤이라도 Properties가 다르면 다른 블록으로 친다.
  정말 대충 요약하면 "생긴게 다르면" 다른 블럭이다. 예를 들어 아래의 경우 A와 B는 서로 다른 레드스톤 블록이다.

 

그렇다면 우리의 목표도 명확해졌다. 이제 NBT 데이터까지 줄인 완벽한 A+B 답안을 만든다.

• Section까지 줄인다. 이제 더이상 한 chunk가 아니라, 한 section 내에서 A+B를 해결한다. (0,0,0)~(15,15,15)
• 가능하다면 Palette에 들어가는 블록 수를 줄인다. (Palette가 4비트면 BlockStates도 4비트 배열, Palette가 5비트면 BlockStates도 5비트 배열이 되기 때문)
  • sandstone, bedrock 등의 사치스러운 블록들 대신 모두 lime_concrete, light_blue_concrete만 사용한다.
  • 항상 파워가 꺼진채로 저장한다. (파워가 다르면 다른 블럭으로 취급함)
  • 리피터, 레버의 경우 최대한 방향/Delay를 똑같게 설치한다.
  • 레드스톤의 경우 솔직히 답이 없는데 적어도 레드스톤 회로가 상승/하강할때는 방향을 맞춘다. (동서남북에 연결된 레드스톤이 자신보다 Y좌표가 위인지 같은지 아래인지도 따져서 Properties가 달라짐)

일주일간의 삽질 끝에 위와 같은 코드를 만들 수 있었다.

여담으로 알려지지 않았던 버그인데 리피터를 일직선으로 3개 놓을때 말고도 위처럼 펜토미노 모양을 만들어도 채점이 똑바로 되지 않는다.

마지막 3틱을 위 코드처럼 펜토미노 모양으로 만들면 357913941점을 맞을 수 있다?????????????????????????

아니 섭테2가 섭테1 부분집합인데 이게 왜 가능한거임

이건 Gemini도 이해를 못 했다 분명 코드상 ban_block을 제외하면 차이점이 없을텐데????????????

 

하지만 진짜 최종 구데기컵 2는 명확하게 "채점코드대로 할테니 마크 믿지 말고 채점코드를 믿으라"고 공지를 했기 때문에 꼬운 사람이 수정하는 수밖에 없다.

펜토미노 모양으로 짰다면 위 코드처럼 리피터를 떨어뜨려서 T자 모양으로 만들면 된다.

 

이제 완벽한 코드가 만들어졌다.

• 1개의 section 안에 모든 코드를 담았다.
• Palette도 31 entries로, 이거보다 더 줄일수도 있겠지만 16 entries 이하는 절대 불가능할것으로 추측되는 바, 이정도면 BlockStates가 최대한 줄어든 상태다.

아까 올린 파이썬 코드를 통해 압축시키고 제출을 하면..?

 

왜 늘어났는데 아오;;;;;;;;;;;;

 

정황상 메타데이터 자체는 현재 코드가 더 적지만, 모종의 이유로 기존 코드가 zopfli이 압축시키기 더 쉬운 형태였던거 같다..?
오늘의 교훈: 잘 돌아가는 코드는 건드리지 말자.....

 

zopfli이 생각보다 더 압축이 뛰어나다는 사실을 알았으니, 개인적인 추측으로는 아예 4개의 section을 사용해서 각 section을 최대한 비슷하게 만들면 zopfli이 압축을 더 잘해서 코드가 더 줄어들 것 같다.

각 섹션의 맨 아래에 input을 넣고, 섹션 위쪽에 adder를 만들어서 하면 괜찮을거 같은데...? 일단 Y=1이랑 Y=2 section은 정확하게 똑같을거라 압축 잘 될거고

 

아니면 채점코드를 더 뜯어봐서 레드스톤이 정확히 어떻게 동작하는지 뜯어봐도 된다. 만약 약간의 "있을 수 없는" 레드스톤이 허용된다면 (옆에 레드스톤이 없는데 properties 상으로는 있는 것처럼 되어있다던가) 수동으로 debug stick을 사용하던가, 아니면 Gemini 시켜서 코드 만들든가 해서 Properties를 더 압축시키고 Blockstates도 따라서 업데이트를 해줄 수 있다.

 

아니면 사실 코드가 mca만 넣어줄거라는 친절한 기대를 하고 있고 나름 대충(?) 짰기 때문에.... binary를 어거지로 바이트 단위로 맞추면 arbitrary code execution도 가능하지 않을까? 하지만 A+B (MC)의 채점과정은 컴파일러와 인터프리터를 거치기 때문에 이 과정은 생각보다 어렵다... 결국 실제 채점은 mca를 바로 실행시키는게 아니라 mca를 컴파일 한 것을 실행시키는거기 때문에 인터프리터에서 A+B를 출력하는 바이너리를 먼저 계산하고, 컴파일러가 그 바이너리를 내뱉도록 하는 mca를 생각해야 한다....

 

뭐 어쨌든 5036B가 최선은 아닌거 같지만 내가 더 이상 시간을 쏟을 여유가 없기도 하고, 백준이 오늘 섭종하는 것도 있어서 여기까지만 해야겠다.

 

Good Bye, BOJ!