[코딩테스트] 격자 시뮬레이션 백트래킹

격자(2D 배열) 위에서 복잡한 시뮬레이션을 진행하면서, 동시에 특정 선택에 대해 백트래킹이 필요한 유형이 있다. 표준 백트래킹처럼 "수정 → 재귀 → 되돌리기"가 통하지 않는 상황이고, 다른 접근이 필요하다.

왜 일반 백트래킹이 어렵나

일반 백트래킹은 이런 구조다.

// 표준 백트래킹: 수정 → 재귀 → 되돌리기
state[i] = chosen;
dfs(next);
state[i] = original;  // 원상 복구

이게 통하려면 "되돌리기"가 간단해야 한다. 배열 한 칸을 원래 값으로 되돌리는 건 쉽다. 그런데 복잡한 시뮬레이션 한 단계 전체를 되돌리는 건 어렵다.

청소년 상어를 예로 들면, 상어가 이동하고 나서 16마리 물고기가 전부 위치를 바꾼다. 이 상태에서 "한 단계 전으로 돌아가기"는 16마리 이동을 전부 역순으로 되돌려야 한다는 뜻이다. 구현할 수 있지만, 실수 위험이 크고 코드가 복잡해진다.

해결책은 간단하다. 되돌리는 대신, 분기 전에 상태를 복사한다.

핵심 패턴: 상태를 복사하고 재귀

각 재귀 호출은 자기만의 독립된 복사본을 갖는다. 한 경로가 원본 상태를 오염시키지 않는다. "되돌리기"가 필요 없다.

코드 구조는 다음과 같다.

void dfs(State state, int score) {
    List<Choice> choices = getChoices(state);

    if (choices.isEmpty()) {
        answer = Math.max(answer, score);
        return;
    }

    for (Choice c : choices) {
        State next = state.deepCopy();   // 상태 복사
        simulate(next, c);              // 복사본에서 시뮬레이션
        dfs(next, score + c.value);     // 재귀
        // 되돌리기 없음 — 원본 state는 건드리지 않음
    }
}

state.deepCopy()가 이 패턴의 핵심이다.

깊은 복사 vs 얕은 복사

이 패턴에서 가장 흔한 버그 원인이다.

격자에 객체가 담겨 있으면, 배열만 복사해서는 안 된다. 배열을 복사해도 안에 있는 객체들은 여전히 같은 참조를 가리킨다.

// 얕은 복사 — 잘못된 방법
Fish[][] copy = Arrays.copyOf(grid, 4);
// copy[0][0] == grid[0][0] (같은 객체!)
// copy[0][0].dir = 3 하면 grid[0][0].dir도 3이 됨

객체 안의 필드까지 전부 새로 만들어야 진짜 독립된 복사본이다.

// 깊은 복사 — 올바른 방법
Fish[][] deepCopy(Fish[][] grid) {
    Fish[][] copy = new Fish[4][4];
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            if (grid[i][j] != null)
                copy[i][j] = new Fish(grid[i][j]);  // 새 객체 생성
    return copy;
}

Fish 클래스에 복사 생성자가 있어야 한다.

class Fish {
    int key, dir, row, col;

    Fish(Fish other) {
        this.key   = other.key;
        this.dir   = other.dir;
        this.row   = other.row;
        this.col   = other.col;
    }
}

메모리와 성능

상태를 복사하는 만큼 메모리가 더 쓰인다. 괜찮은 이유는:

• 격자가 작다 (4×4 = 16칸)
• 재귀 깊이가 제한적이다 (물고기를 먹을 때마다 줄어드니 최대 16번)
• 각 분기의 선택지도 많지 않다 (방향 하나로 최대 3~4칸)

상태 복사 방식은 코드가 단순하고 버그가 적다. 격자가 크거나 재귀 깊이가 깊을 때는 메모리를 고려해야 하지만, 이 문제 수준에서는 문제없다.

이 패턴이 나오는 문제들

공통 특징:

• 격자 위에서 여러 객체가 복잡하게 이동하거나 상호작용
• 특정 시점에 여러 선택지 중 하나를 고르는 분기 존재
• 최댓값/최솟값을 구하는 최적화 문제

대표 문제들:

• BOJ 19236 청소년 상어 → BOJ19236 풀이 가이드
• BOJ 19237 어른 상어 (유사한 구조, 더 복잡한 규칙)
• BOJ 20056 마법사 상어와 파이어볼