[백준 2630번] 색종이 만들기 ( C++/ Python )

아이디어는 아래 분할 정복 문제 풀었던 것과 동일하다. 다만 색종이를 판단해야하는 방법이 추가됐을 뿐.

[백준 1074번] Z ( 분할정복, 재귀) ** 다시풀어보기**

 

2630번: 색종이 만들기

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<string> v;
map<string,int> m;
int board[129][129];
int blue =0;
int white = 0;

bool isSame(int r, int c, int size) // 같은 색종이들인지 완전 탐색
{
    for(int i = r ; i < r+size; i++)
    {
        for(int j = c; j< c+size; j++)
        {
            if(board[i][j] != board[r][c]) // 다른거면
            {
                return false; // 중간에 빠져나옴.
            }
        }
    }
    return true;
}

void dfs(int r, int c, int size)
{
    if(isSame(r,c,size)) // 만약 해당 영역의 색종이가 모두 같은색이라면
    {
        if(board[r][c] == 1) blue +=1; // 해당색에 맞게 count값 +1씩해준다.
        else white += 1;
    }else{
        dfs(r,c,size/2); // 왼쪽 위
        dfs(r,c+size/2,size/2); // 오른쪽 위
        dfs(r+size/2,c,size/2); // 왼쪽 아래
        dfs(r+size/2,c+size/2,size/2); // 오른쪽 아래
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    for(int i = 0; i< N ; i++)
    {
        for(int j = 0 ; j< N; j++)
        {
            int tmp;
            cin >> tmp;
            board[i][j] = tmp;
        }
    }
    dfs(0,0,N);
    cout << white << '\n';
    cout << blue << '\n';
}

파이썬으로도 풀어보자

2차원을 받는건 처음인데..?

Python 풀이

아니 로직 그대로 했는데, 이상하게 런타임에러가 속출했다.

 

board = [list(map(int,input().rstrip().split())) for _ in range(N)]에서

list()로 안묶어주면 런타임에러가 계속 나더라.

그런데 해주나 안해주나 type을 찍어봤을 때 둘다 list던데 뭐가 다른건지 잘 모르겠다. 

심지어 처음부터 런타임에러가 뜨는게 아니라 9%에서 뜨던데.. 뭐는 맞고 뭐가 틀린건지 ..

import sys
input = sys.stdin.readline

N = int(input().rstrip())
white = 0
blue =0
board = [list(map(int,input().rstrip().split())) for _ in range(N)]

def isSame(r,c,size):
    if size ==1:
        return True
    for i in range(r,r+size):
        for j in range(c,c+size):
            if board[i][j] != board[r][c]:
                return False
    return True
    
def dfs(r,c,size):
    global blue, white
    if r>= N or c >=N:
        return
    if isSame(r,c,size) :
        if(board[r][c] ==1):
            blue +=1
        else : 
            white += 1
    else :
        dfs(r,c, size//2)
        dfs(r,c+size//2, size//2)
        dfs(r+size//2,c , size//2)
        dfs(r+size//2, c+size//2, size//2)

dfs(0,0,N)
print(white)
print(blue)