노노그램 겹침법(오버랩) 마스터하기

겹침법 복습

겹침법(Overlap Method)은 노노그램에서 가장 기본적이면서도 강력한 기법입니다. 블록을 가능한 가장 왼쪽(또는 위쪽)과 가장 오른쪽(또는 아래쪽)에 배치했을 때, 두 위치 모두에서 채워지는 칸을 확정하는 방법입니다.

이 글에서는 기본 겹침법을 넘어서, 실전에서 마주치는 복잡한 상황에서도 겹침법을 효과적으로 적용하는 고급 기법을 다룹니다.

단일 블록 겹침의 심화

공식과 직관

줄 길이 L, 블록 크기 N일 때:

• 겹침 칸 수 = 2N - L
• 겹침이 시작되는 위치 = L - N (0-indexed)
• 겹침이 끝나는 위치 = N - 1 (0-indexed)

이 공식을 암기하면 머릿속으로 빠르게 계산할 수 있습니다. 예를 들어 15칸 줄에 단서 10이면 겹침 = 2×10 - 15 = 5칸입니다.

빠른 판단 기준

• 블록이 줄 길이의 절반 초과: 반드시 겹침 발생
• 블록이 줄 길이의 절반 이하: 겹침 없음, 다른 줄 먼저
• 블록이 줄 길이와 같음: 줄 전체 확정

이 기준만으로도 어떤 줄을 먼저 볼지 빠르게 판단할 수 있습니다.

복수 블록 겹침

독립적 범위 계산

여러 블록이 있을 때, 각 블록의 가능 범위를 독립적으로 계산합니다.

15칸 줄, 단서 4 3 2:

먼저 각 블록의 가장 빠른 시작점과 가장 늦은 끝점을 계산합니다:

블록 1 (크기 4):

• 가장 빠른 시작: 0번 칸
• 가장 늦은 끝: 뒤에 3 + 1 + 2 = 6칸이 필요하므로, 15 - 6 - 1 = 8번 칸이 끝
• 가능 범위: 0~8번

블록 2 (크기 3):

• 가장 빠른 시작: 4(블록1 최소) + 1(간격) = 5번 칸
• 가장 늦은 끝: 뒤에 2 = 2칸이 필요하므로, 15 - 2 - 1 = 12번 칸이 끝
• 가능 범위: 5~12번

블록 3 (크기 2):

• 가장 빠른 시작: 5 + 3 + 1 = 9번 칸
• 가장 늦은 끝: 14번 칸
• 가능 범위: 9~14번

각 블록별로 겹침을 계산하면:

• 블록 1: 범위 길이 = 9, 겹침 = 2×4 - 9 = -1 → 없음
• 블록 2: 범위 길이 = 8, 겹침 = 2×3 - 8 = -2 → 없음
• 블록 3: 범위 길이 = 6, 겹침 = 2×2 - 6 = -2 → 없음

이 경우 추가 정보 없이는 아무것도 확정할 수 없습니다.

조밀한 단서

10칸 줄, 단서 3 3 2:

최소 길이 = 3 + 1 + 3 + 1 + 2 = 10 → 줄 길이와 같음!

이 경우 배치는 유일합니다: ■■■□■■■□■■

최소 길이가 줄 길이와 같으면 전체가 확정됩니다. 이런 줄을 가장 먼저 찾아야 합니다.

부분 정보가 있을 때의 겹침

실전에서 가장 강력한 기법은 이미 확보된 정보를 겹침법에 결합하는 것입니다.

채워진 칸 활용

10칸 줄, 단서 3, 6번 칸이 채워져 있음:

6번 칸이 블록에 포함되어야 하므로:

• 블록의 시작은 최대 6번 칸 (블록 크기 3이면 4, 5, 6 또는 5, 6, 7 또는 6, 7, 8)
• 가능한 위치: 시작 4~6번
• 겹침: 모든 가능한 위치에서 6번 칸은 확정 (이미 알고 있음)
• 5번 칸도 모든 위치에서 채워짐 → 5번 칸 확정!

X 표시로 구간 분리

10칸 줄, 단서 2 3, 5번 칸에 X:

줄이 두 구간으로 나뉩니다: 04번 (5칸)과 69번 (4칸).

• 블록 2(크기 3)는 4칸 구간에만 들어갈 수 있음 (5칸 구간에도 가능하지만 블록 2를 먼저 배치해야 함)
• 만약 블록 2가 69번 구간에 확정되면, 블록 1(크기 2)은 04번에 배치
• 6~9번 구간에서 블록 3: 겹침 = 2×3 - 4 = 2칸 → 7, 8번 칸 확정

이처럼 X 표시 하나가 연쇄적으로 많은 정보를 줄 수 있습니다.

양방향 겹침

가로줄과 세로줄의 교차

가로줄에서 확정한 칸은 세로줄의 정보가 됩니다. 세로줄에서 이 정보로 새로운 칸을 확정하면, 다시 가로줄의 정보가 됩니다.

이 순환이 노노그램 풀이의 핵심 루프입니다:

1. 가로줄 겹침으로 칸 확정
2. 세로줄 겹침으로 칸 확정
3. 새로 확정된 칸으로 다시 가로줄 겹침
4. 변화가 없을 때까지 반복

효율적인 순서

모든 줄을 매번 검사하는 것은 비효율적입니다. 새로 확정된 칸이 있는 줄만 재검사하면 됩니다. 정보가 변경된 줄을 큐(queue)에 넣어두고 하나씩 처리하는 방식이 가장 효율적입니다.

겹침법의 한계

겹침법만으로 풀 수 없는 퍼즐도 있습니다. 이런 경우 추가 기법이 필요합니다:

• 모순법(Contradiction): 특정 칸을 가정하고 모순이 발생하면 반대를 확정
• 색칠법(Coloring): 블록 번호를 기반으로 가능한 조합 추적
• 시행착오(Trial and Error): 최후의 수단, 숙련자는 거의 사용하지 않음

하지만 대부분의 퍼즐(특히 15×15 이하)은 겹침법과 기본 추론만으로 풀 수 있습니다.

실전 연습 팁

noguelike.com의 던전 모드에서는 층이 깊어질수록 격자가 커집니다. 5×5에서 겹침법의 기초를 다지고, 10×10에서 복수 블록 겹침을 연습하고, 15×15에서 부분 정보 활용을 익히세요.

타이머가 있는 환경에서 연습하면 겹침 계산 속도가 자연스럽게 빨라집니다. 처음에는 공식을 의식적으로 적용하다가, 나중에는 패턴을 보자마자 직관적으로 겹침을 파악하게 됩니다.

마무리

겹침법은 노노그램의 알파이자 오메가입니다. 기본 원리는 단순하지만, 복수 블록 범위 계산, 부분 정보 활용, 양방향 교차 적용까지 익히면 거의 모든 퍼즐을 체계적으로 풀 수 있습니다. 꾸준히 연습하면 계산 속도가 빨라지고, 결국 “보자마자 아는” 수준에 도달합니다.