[백준] 1780. 종이의 개수 풀이

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

 

만일 전체 배열의 값이 동일하지 않으면 종이를 9등분을 한 후 각각의 2차원 배열들이 동일한 값을 가지는지 검사를 하는 방식으로 문제를 해결하였다. 

이 과정에서 재귀함수를 사용해야겠다는 판단을 하였다.

 

우선 전체 배열을 v에 저장하고, f함수에서 해당 배열의 값들이 전부 동일한지 same함수를 이용해 검사한다.
만일 동일하다면 동일한 값에 해당하는 변수에 1을 더한다.(numM1 = -1, num0 = 0, num1 = 1)
동일하지 않다면 배열을 9등분하여 다시 검사한다.(재귀)
검사하는 배열의 크기가 1x1이 될때까지 반복한 후 numM1, num0, num1의 값을 출력한다.

 

---

C

더보기

#include <stdio.h>

int v[2187][2187];
int num1, num0, numM1;
int same(int x, int y, int r){
    int a = v[x][y];
    for(int i = x; i < x+r; i++){
        for(int j = y; j < y+r; j++){
            if(a != v[i][j]) return 0; // 범위 내 숫자 동일x
    }}
    if(a == 1) num1++;
    if(a == 0) num0++;
    if(a == -1) numM1++;
    return 1; // 범위 내 숫자 동일o
}

int f(int r, int start_x, int start_y){
    if(same(start_x, start_y, r)) return 0; // 주어진 전체 배열 숫자 동일 
    for(int i = start_x; i < start_x + r; i += r/3){
        for(int j = start_y; j < start_y + r; j += r/3){
            // 범위 내 숫자 동일하지 않으면 재귀
            if(same(i, j, r/3) == 0) f(r/3, i, j);
    }}
    return 0;
}

int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &v[j][i]);
    }}
    
    f(n, 0, 0);
    printf("%d\n%d\n%d", numM1, num0, num1);
}

---

Python

더보기

def same(x, y, r):
    global v; global num1; global num0; global numM1
    a = v[x][y]
    for i in range(x, x+r):
        for j in range(y, y+r):
            if a != v[i][j]: return 0
    if a == 1: num1 += 1
    if a == 0: num0 += 1
    if a == -1: numM1 += 1
    return 1;

def f(r, start_x, start_y):
    if same(start_x, start_y, r): return 0
    i = start_x
    while i < start_x + r:
        j = start_y
        while j < start_y + r:
            if same(i, j, r//3) == 0: f(r//3, i, j)
            j += r // 3
        i += r // 3
    return 0

n = int(input())
num1 = 0; num0 = 0; numM1 = 0
v = [[0 for i in range(2187)] for i in range(2187)]
for i in range(n):
    ip = list(map(int, input().split(" ")))
    for j in range(n):
        v[j][i] = ip[j]

f(n, 0, 0)
print("%d\n%d\n%d" % (numM1, num0, num1))