완전탐색 — 격자 탐색

관련 문제

문제	난이도	핵심
카펫	Lv.2	테두리 공식
게임 맵 최단거리	Lv.2	격자 BFS
전력망을 둘로 나누기	Lv.2	격자 완전탐색

---

1. 개념

격자 탐색은 2차원 배열(격자)에서 가능한 모든 경우를 탐색하는 방식이다.

완전탐색의 일종이지만, 상하좌우 이동이나 테두리 계산처럼 격자 구조에 특화된 패턴이 자주 등장한다.

B B B B
B Y Y B   ← 이런 격자 구조에서
B B B B     테두리(B)와 내부(Y)를 구분하는 문제

---

2. 동작 과정

카펫 — brown=10, yellow=2 인 경우

전체 칸 수 = 12. 12의 약수 쌍 (w, h)를 구하면서 테두리 조건을 검증한다.

w	h	w >= h	2*(w+h)-4	== brown?
12	1	✅	22	❌
6	2	✅	12	❌
4	3	✅	10	✅ → 정답

---

3. 핵심 공식

직사각형 테두리 칸 수

brown = 2 * (w + h) - 4

왜 -4인가? 가로 w개 + 세로 h개를 2번씩 더하면 네 모서리가 중복으로 카운트되기 때문이다.

B B B B   ← w개
B     B
B B B B   ← w개
↑       ↑
h개     h개

2*(w+h) 에서 모서리 4개 중복 → -4

상하좌우 이동 (4방향)

int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};

for (int d = 0; d < 4; d++) {
    int nx = x + dx[d];
    int ny = y + dy[d];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
        // 유효한 범위 내에서 이동
    }
}

8방향 이동

int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

---

4. 핵심 포인트 2가지

약수 탐색으로 가로/세로 후보를 구해라

격자 크기를 구하는 문제는 전체 칸 수의 약수를 구하는 것에서 시작한다.

int total = brown + yellow;
for (int h = 1; h <= total; h++) {
    if (total % h == 0) {
        int w = total / h;
        // w, h로 조건 검증
    }
}

범위 체크를 빠뜨리지 마라

격자를 벗어나는 인덱스에 접근하면 ArrayIndexOutOfBoundsException이 난다. 이동 전에 반드시 범위를 확인해야 한다.

if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
    // 이동
}

---

5. 시간복잡도

유형	시간복잡도	비고
약수 탐색	O(N)	전체 칸 수만큼 순회
격자 완전탐색	O(N × M)	모든 칸 탐색
격자 BFS	O(N × M)	각 칸을 최대 한 번 방문

---

6. 주의사항

• 테두리 공식 2*(w+h)-4를 외워라. 카펫 유형 문제에서 거의 항상 나온다.
• 가로 >= 세로 조건을 확인해라. 문제에서 가로가 세로보다 길거나 같다고 명시하는 경우가 많다. w >= h 조건을 빠뜨리면 중복 답이 나온다.
• 범위 체크는 이동 전에 해라. nx, ny 계산 후 배열에 접근하기 전에 반드시 범위를 확인해야 한다.
• 방향 배열 dx, dy는 세트로 관리해라. 인덱스가 맞지 않으면 엉뚱한 방향으로 이동한다.