[백준] 2630. 색종이 만들기

안녕하세요.

이번에는 백준의 단계별로 풀어보기 중 분할정복의 '색종이 만들기'를 풀어보겠습니다.

문제설명

https://www.acmicpc.net/problem/2630

 

전형적인 분할정복문제이다.

입력

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

출력

9
7

나의 사고과정

예전에 이런것을 풀어봤었다! 제일 큰 종이에서 모든 부분이 같은지 확인하고 만약 아니라면 4부분으로 나눠서 똑같이 확인한다. 모두 같은 부분이 나오면 해당 색깔의 종이 수를 세준다.

소스코드

C++

#include <cstdio>
#include <cstring>

const int TS = 128;

void printta(int ta[TS][TS], int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            printf("%d%c", ta[i][j], " \n"[j == n-1]);
        }
    }
}

int white = 0;
int blue = 0;

bool isSameColor(int x, int y, int a, int b, int ta[TS][TS], int color) {
    for (int i = x; i < a; ++i) {
        for (int j = y; j < b; ++j) {
            if (ta[i][j] != color) {
                return false;
            }
        }
    }
    return true;
}

bool isWhite(int x, int y, int a, int b, int ta[TS][TS]) {
    return isSameColor(x, y, a, b, ta, 0);
}

bool isBlue(int x, int y, int a, int b, int ta[TS][TS]) {
    return isSameColor(x, y, a, b, ta, 1);
}

void solve(int x, int y, int a, int b, int ta[TS][TS]) {
    if (isWhite(x, y, a, b, ta)) {
        ++white;
    } else if (isBlue(x, y, a, b, ta)) {
        ++blue;
    } else {
        int mx = (a+x)/2;
        int my = (b+y)/2;
        solve(x, y, mx, my, ta);
        solve(mx, my, a, b, ta);
        solve(mx, y, a, my, ta);
        solve(x, my, mx, b, ta);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int ta[TS][TS];
    memset(ta, 0, sizeof(ta));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &ta[i][j]);
        }
    }

    solve(0, 0, n, n, ta);
    printf("%d\n%d\n", white, blue);
}

Python3

black = white = 0

def is_same_color(ta):
    c = ta[0][0]
    for vv in ta:
        for i in vv:
            if c != i:
                return False
    return True

def solve(ta, size):
    if is_same_color(ta):
        global black, white
        if ta[0][0] == 1:
            black += 1
        else:
            white += 1
    else:
        m = int(size/2)
        solve([v[:m] for v in ta[:m]], m)
        solve([v[m:] for v in ta[:m]], m)
        solve([v[:m] for v in ta[m:]], m)
        solve([v[m:] for v in ta[m:]], m)
        
        
n = int(input())
ta = [[ int(v) for v in input().split() ] for _ in range(n)]

solve(ta, n)

print(white, black, sep='\n')

Golang

package main

import (
	"bufio"
	"fmt"
	"os"
)

var in = bufio.NewReader(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func scanf(s string, a ...interface{})  { fmt.Fscanf(in, s, a...) }
func printf(s string, a ...interface{}) { fmt.Fprintf(out, s, a...) }

func isSameColor(x, y, a, b int, ta [][]int) bool {
	color := ta[x][y]
	for i := x; i < a; i++ {
		for j := y; j < b; j++ {
			if color != ta[i][j] {
				return false
			}
		}
	}
	return true
}

var blue = 0
var white = 0

func solve(x, y, a, b int, ta [][]int) {
	if isSameColor(x, y, a, b, ta) {
		if ta[x][y] == 1 {
			blue++
		} else {
			white++
		}
	} else {
		mx := (x + a) / 2
		my := (y + b) / 2
		solve(x, y, mx, my, ta)
		solve(x, my, mx, b, ta)
		solve(mx, y, a, my, ta)
		solve(mx, my, a, b, ta)
	}
}

func main() {
	var n int
	scanf("%d\n", &n)

	ta := make([][]int, n)
	for i := 0; i < n; i++ {
		ta[i] = make([]int, n)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			scanf("%d ", &ta[i][j])
		}
	}

	solve(0, 0, n, n, ta)
	printf("%d\n%d\n", white, blue)
	out.Flush()
}

결과