[알고리즘] 격자판 슬라이딩 탐색 유형 — 브루트포스 + 2D 패턴 매칭

격자판 슬라이딩 탐색 — 브루트포스 + 2D 패턴 매칭

1. 이 유형이 나오는 상황

두 개의 격자(grid)가 주어지고, 한 격자를 다른 격자 위에 겹쳐가면서 최적의 위치를 찾아야 할 때 등장한다.

핵심 질문은 항상 이것이다.

*"두 격자를 어떻게 겹쳐야 공통 원소가 최대가 되는가?"*

대표 문제:

• 동전 퍼즐 — 현재 배치 → 목표 배치로 만들 때 최소 이동 횟수
• 자물쇠와 열쇠 — 열쇠를 회전/반전해서 자물쇠에 맞추기

---

2. 핵심 아이디어 — 왜 "겹치기"인가?

동전 퍼즐을 예로 들면:

현재(vec1):    목표(vec2):
O . .          . O .
. O .          . . O

동전을 옮기는 최소 횟수를 구하려면 반대로 생각한다.

"이미 목표 위치에 있는 동전이 많을수록 → 옮길 동전이 적다"

따라서:

정답 = 전체 동전 수 - 최대한 겹쳤을 때의 동전 수

"최대한 겹친다"는 것이 곧 vec1을 고정하고 vec2를 모든 방향으로 밀어보는 것이다.

---

3. 오프셋(offset) — vec2를 밀어보는 방법

오프셋 (dy, dx) = vec2를 얼마나 이동할지를 나타내는 값이다.

dy=0, dx=1 일 때 (vec2를 오른쪽으로 1칸):

vec1:          vec2(이동 후):
O . .          . O .   ← dx=1이므로 열이 1씩 밀림
. O .          . . O

실제 코드에서는, vec1의 좌표에 오프셋을 더해 vec2의 좌표를 계산한다.

int h2 = h1 + dy;
int w2 = w1 + dx;
// vec1[h1][w1]이 vec2[h2][w2]와 겹치는지 확인

오프셋 범위는 왜 -H1+1 ~ H2-1 인가?

←── 완전히 벗어남 ──┬── 겹치는 구간 ──┬── 완전히 벗어남 ──→
                 │              │
           dy = -(H1-1)     dy = (H2-1)

vec1과 vec2가 단 한 칸이라도 겹칠 수 있는 모든 위치를 탐색하는 것이다.

---

4. 전체 코드 (오프셋 탐색)

동전 퍼즐 문제의 예시 코드를 살펴보자

int main() {
    int H1, W1;
    cin >> H1 >> W1;
    vector<string> vec1(H1);
    int totalCoins = 0;
    for (int i = 0; i < H1; i++) {
        cin >> vec1[i];
        for (char c : vec1[i])
            if (c == 'O') totalCoins++;
    }

    int H2, W2;
    cin >> H2 >> W2;
    vector<string> vec2(H2);
    for (int i = 0; i < H2; i++) cin >> vec2[i];

    int maxOverlap = 0;

    for (int dy = -H1 + 1; dy < H2; dy++) {
        for (int dx = -W1 + 1; dx < W2; dx++) {
            int overlap = 0;
            for (int i = 0; i < H1; i++) {
                for (int j = 0; j < W1; j++) {
                    int h2 = i + dy;
                    int w2 = j + dx;

                    // 범위 체크 필수
                    if (h2 >= 0 && h2 < H2 && w2 >= 0 && w2 < W2)
                        if (vec1[i][j] == 'O' && vec2[h2][w2] == 'O')
                            overlap++;
                }
            }
            maxOverlap = max(maxOverlap, overlap);
        }
    }

    cout << totalCoins - maxOverlap << endl;
    return 0;
}

자주 하는 실수

실수	증상
dy < H2 - 1 로 쓰기	마지막 케이스 탐색 누락
vec2[i+dy][j+dx] 범위 체크 없이 접근	런타임 에러 (index out of range)
H1, W1을 변환 후에도 그대로 쓰기	회전 후 크기가 바뀌는 경우 틀림

---

5. 변환 추가하기 — 회전 & 반전

자물쇠와 열쇠 같은 문제에서는 열쇠를 회전하거나 뒤집는 조건도 추가된다.

이 경우 vec1의 모든 변환 버전을 생성한 뒤, 각각에 대해 오프셋 탐색을 돌린다.

좌우 반전 (flipLR)

O . .          . . O
. O .    →     . O .
. . .          . . .

각 행(row)의 문자 순서를 뒤집는다.

vector<string> flipLR(vector<string>& v) {
    vector<string> res = v;
    for (auto& row : res)
        reverse(row.begin(), row.end());  // 문자 순서 반전
    return res;
}

상하 반전 (flipUD)

O . .          . . .
. . .    →     . . .
. . .          O . .

행(row)들의 순서를 뒤집는다.

vector<string> flipUD(vector<string>& v) {
    vector<string> res = v;
    reverse(res.begin(), res.end());  // 행 순서 반전
    return res;
}

90도 시계방향 회전 (rotate90)

O . .          . . O
. O .    →     . O .
. . .          . . .

중요: 회전하면 H×W → W×H 로 크기가 바뀐다.

vector<string> rotate90(vector<string>& v) {
    int H = v.size(), W = v[0].size();
    vector<string> res(W, string(H, '.'));  // W×H 크기로 새로 생성
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            **res[j][H - 1 - i] = v[i][j];**
    return res;
}

변환식 res[j][H-1-i] = v[i][j] 유도 과정

시계방향 90도 회전은 두 단계로 나뉜다.

step 1. 행과 열을 교환:  (i, j)      → (j, i)
step 2. 열을 뒤집기:     (j, i)      → (j, H-1-i)

한 줄 요약:

열이 새 행이 되고, 원본 행은 뒤집혀서 새 열이 된다.

8가지 변환 생성 & 탐색

원본을 0°, 90°, 180°, 270° 회전하고, 각각에 좌우 반전을 적용하면 총 8가지 변환이 나온다.

vector<vector<string>> candidates;

vector<string> tmp = vec1;
for (int rot = 0; rot < 4; rot++) {
    candidates.push_back(tmp);           // 회전본
    candidates.push_back(flipLR(tmp));   // 회전본 + 좌우반전
    tmp = rotate90(tmp);                 // 다음 회전
}

// 각 변환에 대해 오프셋 탐색
for (auto& cand : candidates) {
    int H1 = cand.size(), W1 = cand[0].size();  // 크기 다시 계산!

    for (int dy = -H1 + 1; dy < H2; dy++) {
        for (int dx = -W1 + 1; dx < W2; dx++) {
            int overlap = 0;
            for (int i = 0; i < H1; i++) {
                for (int j = 0; j < W1; j++) {
                    int h2 = i + dy, w2 = j + dx;
                    if (h2 >= 0 && h2 < H2 && w2 >= 0 && w2 < W2)
                        if (cand[i][j] == 'O' && vec2[h2][w2] == 'O')
                            overlap++;
                }
            }
            maxOverlap = max(maxOverlap, overlap);
        }
    }
}

상하반전이 없는 이유

• 회전본
• 회전본 + 좌우반전
• 회전본 + 상하반전 ← ??
• 다음회전

상하반전이 다른 변환의 조합으로 만들어지기 때문에 만들지 않아도 된다

---

6. 풀이 전략 정리

1. vec1 고정, vec2를 모든 오프셋(dy, dx)으로 이동
2. 각 오프셋에서 O끼리 겹치는 개수 계산
3. 최대 겹침 = maxOverlap
4. 정답 = totalCoins - maxOverlap

회전/반전이 허용되는 경우:
  → vec1의 8가지 변환 버전 생성
  → 각 버전마다 동일하게 오프셋 탐색
  → 변환 후에는 H1, W1 크기를 반드시 다시 계산

---

7. 시간복잡도

조건	복잡도
기본 오프셋 탐색	$O((H1+H2) × (W1+W2) × H1 × W1)$
8가지 변환 포함	위의 8배

H1, H2, W1, W2가 크지 않은 경우(보통 50 이하)에 유효한 전략이다.