BOJ : 2630 색종이 만들기

박정무·2021년 12월 21일
0

Algorithm

목록 보기
4/7
post-thumbnail

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.


어떻게 풀 것이냐?

과정을 생략하고 풀이를 보고싶은 사람은 맨 아래로

접근방식 : N/2 x N/2의 문제로 나누어 생각하면 편하겠다!

NxN 의 정사각형에서 하나의 숫자로 이루어지지 않았다면?
→ N/2 x N/2 의 정사각형 4개로 쪼개서 다시 검사하자!
→ 재귀...? 라고 생각이 들었다.

재귀함수를 정의할 때 가장 중요하게 생각하는 것은

  1. 전달되는 파라미터
  2. 탈출조건
  3. 반환값의 유무

이다.

  1. 재귀함수의 파라미터로 반으로 짤린 정사각형의 2차원 배열을 전부 전달하기보다는 배열의 인덱스를 전달하는 것이 좋겠다.
    배열의 인덱스를 전달하면 검사해야하는 정사각형의 크기를 알 수 없다! 크기가 필요하다.
  2. 탈출조건은 정사각형의 크기가 1일때!
  3. 파란색 종이🔷 와 흰색 종이 ⬜ 의 갯수를 반환하면 좋겠다고 생각했다.

일단은 이렇게 생각했다. 코딩을 하면서 바뀔 수 있겠다.
그럼 일단 입출력부터 정의해보자.

기본 입출력 정의


#include <iostream>
#include <vector>

using namespace std;

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

    int t; cin>>t;

 	//2차원 vector 동적 할당.
    vector<vector<int>> v(t,vector<int>(t,0));

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cin >> v[i][j];
        }
    }

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }
}

vector로 입력받을까 array로 입력받을까 고민했는데
함수에 동적 2차원 배열을 전달하는 방법을 몰라서 vector로 선언.
vector가 편합니다...함수에 2차원 배열 전달 하는 법 몰라요 😭

재귀함수 정의

(파란색 종이🔷 의 갯수, 흰색 종이⬜ 의 갯수) 두개를 반환해야하니 pair<int,int>를 생각했다.

Parameter 로는 가로 인덱스, 세로 인덱스, 정사각형 사이즈, 2차원 배열 전체 를 전달받자!

🛑 여기서 잠깐! 🛑

원래는 재귀함수에서 파란색 종이🔷 의 갯수, 흰색 종이⬜ 의 갯수를 반환하고, 더해주는 재귀함수를 생각했다.

근데 종이 갯수를 저장하는 배열을 전역변수로 선언하여 재귀함수에서 접근할 수 있도록 하면 편하겠다는 생각이 들었다!

흰색종이는 0, 파란색 종이는 1이니

arr[0] → 흰색 종이 갯수

arr[1] → 파란색 종이 갯수

🙂 이거지

🚢 Keep going

배열을 검사하고, 하나의 종이로 이루어져 있지 않으면 재귀함수 4개를 호출한다.

검사를 어떻게 할지 고민하다가 이전값하고 다르면 하나의 종이로 이루어져 있지 않다고 생각하기로 했다!

void recur(vector<vector<int>> &v,int horizonIndex, int verticalIndex, int squareSize){
    if(squareSize == 1){
        //인덱스의 종이 숫자++
        white_blue[v[verticalIndex][horizonIndex]] ++;
    }

    // 종이 검사하기
    int beforeValue = v[verticalIndex][horizonIndex];
    for(int i=0;i<squareSize;i++){
        for(int j=0;j<squareSize;j++){
            if(beforeValue == v[verticalIndex+i][horizonIndex+j]) {
                if(i==squareSize-1 && j==squareSize-1){
                    cout<<"검사 통과!"<<endl;
                    white_blue[beforeValue]++;
                }
                beforeValue = v[verticalIndex+i][horizonIndex+j];
            }
            else{
                recur(v,horizonIndex,verticalIndex,squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex,squareSize/2);
                recur(v,horizonIndex,verticalIndex+(squareSize/2),squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex+(squareSize/2),squareSize/2);
                break;
            }
        }
    }
}

이 함수를 호출해주자.

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

    int t; cin>>t;

    vector<vector<int>> v(t,vector<int>(t,0));

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cin >> v[i][j];
        }
    }

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cout<<v[i][j]<<" ";
        }
        cout<<"\n";
    }

    recur(v,0,0,t);
    cout<<"white : "<<white_blue[0]<<"\n";
    cout<<"blue : "<<white_blue[1]<<"\n";

    return 0;
}

우오아아아...한번에 에러없이 예제가 풀렸다!

제출하기 전에 Check할 것!

  1. 입력, 계산, 출력값이 int의 자료를 넘어가는가? (int = 2,147,483,648)
  2. 작은 값의 입력을 잘 해결하는가? (1, 2 정도의 입력을 해보자)
  3. 불필요한 log들 전부 지우고 제출해봅시당.

🙆 제출하러 갑시다 🤘


제출해도 정답이였다 :)
조아요~ ☺️

😀 FULL CODE 🤨



#include <iostream>
#include <vector>

using namespace std;

int white_blue[2] = {0,0};

void recur(vector<vector<int>> &v,int horizonIndex, int verticalIndex, int squareSize){
    if(squareSize == 1){
        //인덱스의 종이 숫자++
        white_blue[v[verticalIndex][horizonIndex]] ++;
        return;
    }

    // 종이 검사하기
    int beforeValue = v[verticalIndex][horizonIndex];
    for(int i=0;i<squareSize;i++){
        for(int j=0;j<squareSize;j++){
            // 이전값과 같으면??
            if(beforeValue == v[verticalIndex+i][horizonIndex+j]) {
                if(i==squareSize-1 && j==squareSize-1){
                    //검색이 끝나면 종이 ++
                    white_blue[beforeValue]++;
                }
                //이전값 갱신!
                beforeValue = v[verticalIndex+i][horizonIndex+j];
            }
            else{
                //재귀는 1사분면, 2사분면, 3사분면, 4사분면 4개!
                recur(v,horizonIndex,verticalIndex,squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex,squareSize/2);
                recur(v,horizonIndex,verticalIndex+(squareSize/2),squareSize/2);
                recur(v,horizonIndex+(squareSize/2),verticalIndex+(squareSize/2),squareSize/2);
                return;
            }
        }
    }
}

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

    int t; cin>>t;

    vector<vector<int>> v(t,vector<int>(t,0));

    for(int i=0;i<t;i++) {
        for (int j = 0; j < t; j++) {
            cin >> v[i][j];
        }
    }

    recur(v,0,0,t);
    cout<<white_blue[0]<<"\n"<<white_blue[1];
    return 0;
}

🤜 FeedBack 🤛


  1. 솔직히 지금까지 재귀함수는 별로 좋지 않다고 생각하고 있었는데 재귀함수는 강력한 것 같다.
    큰 범위 → 작은 범위로 쪼개지는 문제는 재귀를 통해서 해결할 수 있겠다!
  2. 코드가 못생겼다. 다른 사람들이 잘 알아볼 수는 있을까?
    이쁜 코드를 찾아보고 이쁜 코드를 작성하는 방법을 정리해야겠다.

Raeyoung's feedback

  1. 이전 값과 계속 비교할 필요가 없다! 그냥 첫번째 값과 계속 비교하면 됨
    → 이전값 갱신이 불필요한 코드라는 것.
  2. vertical.... horizon.... 괜히 코드만 길어지는 것. → 편하게 matrix[y][x]로 가자.
  3. const nl = "\n";
    cout << nl;

profile
박붕어입니다.

0개의 댓글