[BOJ 1780] 종이 접기

썸네일

최근 DFS나 백트래킹 유형을 풀 때 재귀 함수를 구현하는 것이 어려워서 당분간은 재귀 유형을 풀면서 재귀 연습을 하고자 한다!

이번에 풀 문제는 백준 1780번 종이의 개수라는 문제이다.

1780번: 종이의 개수

 

문제 설명

예제 설명

예제를 도식화

 

구현 아이디어

전체 구현 과정

1. 모두 같은 수 A라면 A로만 채워진 종이의 개수를 +1한다
2. -1, 0, 1로 채워진 종이의 개수를 구하기 위해 map을 사용 (ex. 각각 3, 2, 1장일 때 { (-1,3), (0,2), (1,1) }로 저장된다.
3. 종이의 수가 모두 같지 않다면 종이를 9개로 나눈다 (재귀 사용)

전체 구현 과정은 위와 같이 3단계로 나눌 수 있다.

 

이제 재귀 함수를 만들어보자.

재귀 함수

인자

재귀 함수의 인자는 시작점(좌상단)과 끝점(우하단)이 되어야 한다.

처음에는 인자를 배열로 담으려고 했으나, 그렇게 되면 큰 배열 1개를 작은 배열 9개로 만드는 로직이 복잡해져서 인자를 좌표로 사용했다.

// 시작점 - (sx, sy)
// 끝점 - (ex, ey)
void go(int sx, int sy, int ex, int ey) {
}

 

종료 조건

종료 조건은 종이 안의 수가 모두 같을 경우이다.

시작점의 원소를 target으로 하여 이중 반복문을 통해 target과 다른 값이 하나라도 있다면 false가 되도록 하였다.

bool allSame(int sx, int sy, int ex, int ey) {
    int target = v[sx][sy];
    for (int i = sx; i <= ex; ++i) {
        for (int j = sy; j <= ey; ++j) {
            if (v[i][j] != target) return false;
        }
    }

    return true;
}

 

재귀 호출

큰 배열 1개를 작은 배열 9개로 나누게 되므로 자기 자신을 9개 호출해주어야 한다.

재귀 호출 부분은 대충 아래와 같은 꼴이 될 것이다.

 

void go(int sx, int sy, int ex, int ey) {
    // 종료 조건 생략

    // 재귀 호출
    go();
    go();
    go();
    go();
    go();
    go();
    go();
    go();
    go();
}

 

이제 각 함수에 어떤 인자가 들어가야 할지 생각해보자.

큰 종이의 한 변의 길이를 3k라고 하면 작은 종이의 한 변의 길이 k는 (ex-sx+1)/3이 된다.

 

9분할 과정 도식화

9개 종이의 모든 시작점과 끝점을 sx, sy, k로 표현하면 아래와 같다.

int k = (ex - sx + 1) / 3;

go(sx, sy, sx+k-1, sy+k-1); // 1
go(sx, sy+k, sx+k-1, sy+2*k-1); // 2
go(sx, sy+2*k, sx+k-1, sy+3*k-1); // 3

go(sx+k, sy, sx+2*k-1, sy+k-1); // 4
go(sx+k, sy+k, sx+2*k-1, sy+2*k-1); // 5
go(sx+k, sy+2*k, sx+2*k-1,sy+3*k-1); // 6

go(sx+2*k, sy, sx+3*k-1, sy+k-1); // 7
go(sx+2*k, sy+k, sx+3*k-1, sy+2*k-1); // 8
go(sx+2*k, sy+2*k, sx+3*k-1, sy+3*k-1); // 9

9줄은 너무 많은 것 같고, 3개씩 묶어서 보았을 때 규칙이 보이는 것 같아서 위 코드를 반복문을 사용해서 줄여볼까 했는데 9개를 그대로 쓰는 것이 코드를 이해할 때 더 편할 것 같아 리팩토링은 하지 않았다!

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> v;
map<int, int> ret;

bool allSame(int sx, int sy, int ex, int ey) {
    int target = v[sx][sy];
    for (int i = sx; i <= ex; ++i) {
        for (int j = sy; j <= ey; ++j) {
            if (v[i][j] != target) return false;
        }
    }

    return true;
}

void go(int sx, int sy, int ex, int ey) {
    if (allSame(sx, sy, ex, ey)) { // 종료 조건
        ret[v[sx][sy]] += 1; // Key: -1, 0, 1, Value: 종이가 몇 장인지
        return;
    }

    int k = (ex - sx + 1) / 3;

    go(sx, sy, sx+k-1, sy+k-1);
    go(sx, sy+k, sx+k-1, sy+2*k-1);
    go(sx, sy+2*k, sx+k-1, sy+3*k-1);

    go(sx+k, sy, sx+2*k-1, sy+k-1);
    go(sx+k, sy+k, sx+2*k-1, sy+2*k-1);
    go(sx+k, sy+2*k, sx+2*k-1,sy+3*k-1);

    go(sx+2*k, sy, sx+3*k-1, sy+k-1);
    go(sx+2*k, sy+k, sx+3*k-1, sy+2*k-1);
    go(sx+2*k, sy+2*k, sx+3*k-1, sy+3*k-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 입력
    cin >> n;
    for (int i = 0; i < n; ++i) {
        vector<int> row;
        for (int j = 0; j < n; ++j) {
            int temp;
            cin >> temp;
            row.push_back(temp);
        }
        v.push_back(row);
    }

    go(0, 0, n-1, n-1);

    // 출력
    cout << ret[-1] << "\n";
    cout << ret[0] << "\n";
    cout << ret[1] << "\n";

    return 0;
}