글 읽기 - 쿼드트리 문제점을 찾지 못하겠습니다.

oin0107 8년 전 0

샘플 테스트케이스랑 제가 만든 테스트케이스로는 다 정상적으로 나옵니다.

유사 질문글들 검색해봤지만 그 글에 나온 문제점은 제 소스코드에 해당하지 않았습니다.

혹시 N이 1일때 (0) 또는 (1) 이런식으로 나와야하나 싶어서 수정해봤지만 이것도 아닌 것 같습니다.

도움 부탁드립니다.

#include <iostream>
using namespace std;

char Data[65][65] = { 0, };
char Result[500] = { 0, };
int N;
int idx = 0;

void LU(int Y, int X, int k);
void RU(int Y, int X, int k);
void LD(int Y, int X, int k);
void RD(int Y, int X, int k);

void LU(int Y, int X, int k) {
    int cnt0, cnt1, flag;
    cnt0 = 0; cnt1 = 0; flag = 0;
    Result[idx++] = '(';
    if (k % 2 == 0) {
        for (int i = Y; i < Y + k; i++) {
            for (int j = X; j < X + k; j++) {
                if (Data[i][j] == '0') cnt0++;
                else if (Data[i][j] == '1') cnt1++;
                if (cnt0 != 0 && cnt1 != 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                LU(Y, X, k / 2);
                RU(Y, X + k / 2, k / 2);
                LD(Y + k / 2, X, k / 2);
                RD(Y + k / 2, X + k / 2, k / 2);
                break;
            }
        }
        if (flag == 0) {
            if (cnt0 == (k*k)) Result[idx++] = '0';
            else Result[idx++] = '1';
        }
    }
    else {
        if (Data[Y][X] == '0') Result[idx++] = '0';
        else if (Data[Y][X] == '1') Result[idx++] = '1';
    }
}

void RU(int Y, int X, int k) {
    int cnt0, cnt1, flag;
    cnt0 = 0; cnt1 = 0; flag = 0;
    if (k % 2 == 0) {
        for (int i = Y; i < Y + k; i++) {
            for (int j = X; j < X + k; j++) {
                if (Data[i][j] == '0') cnt0++;
                else if (Data[i][j] == '1') cnt1++;
                if (cnt0 != 0 && cnt1 != 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                LU(Y, X, k / 2);
                RU(Y, X + k / 2, k / 2);
                LD(Y + k / 2, X, k / 2);
                RD(Y + k / 2, X + k / 2, k / 2);
                break;
            }
        }
        if (flag == 0) {
            if (cnt0 == (k*k)) Result[idx++] = '0';
            else Result[idx++] = '1';
        }
    }
    else {
        if (Data[Y][X] == '0') Result[idx++] = '0';
        else if (Data[Y][X] == '1') Result[idx++] = '1';
    }
}

void LD(int Y, int X, int k) {
    int cnt0, cnt1, flag;
    cnt0 = 0; cnt1 = 0; flag = 0;
    if (k % 2 == 0) {
        for (int i = Y; i < Y + k; i++) {
            for (int j = X; j < X + k; j++) {
                if (Data[i][j] == '0') cnt0++;
                else if (Data[i][j] == '1') cnt1++;
                if (cnt0 != 0 && cnt1 != 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                LU(Y, X, k / 2);
                RU(Y, X + k / 2, k / 2);
                LD(Y + k / 2, X, k / 2);
                RD(Y + k / 2, X + k / 2, k / 2);
                break;
            }
        }
        if (flag == 0) {
            if (cnt0 == (k*k)) Result[idx++] = '0';
            else Result[idx++] = '1';
        }
    }
    else {
        if (Data[Y][X] == '0') Result[idx++] = '0';
        else if (Data[Y][X] == '1') Result[idx++] = '1';
    }
}

void RD(int Y, int X, int k) {
    int cnt0, cnt1, flag;
    cnt0 = 0; cnt1 = 0; flag = 0;
    if (k % 2 == 0) {
        for (int i = Y; i < Y + k; i++) {
            for (int j = X; j < X + k; j++) {
                if (Data[i][j] == '0') cnt0++;
                else if (Data[i][j] == '1') cnt1++;
                if (cnt0 != 0 && cnt1 != 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                LU(Y, X, k / 2);
                RU(Y, X + k / 2, k / 2);
                LD(Y + k / 2, X, k / 2);
                RD(Y + k / 2, X + k / 2, k / 2);
                break;
            }
        }
        if (flag == 0) {
            if (cnt0 == (k*k)) Result[idx++] = '0';
            else Result[idx++] = '1';
        }
    }
    else {
        if (Data[Y][X] == '0') Result[idx++] = '0';
        else if (Data[Y][X] == '1') Result[idx++] = '1';
    }
    Result[idx++] = ')';
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Data[i];
	if (N == 1) cout << "(" << Data[0] << ")" << endl;
	else {
		LU(0, 0, N / 2);
		RU(0, N / 2, N / 2);
		LD(N / 2, 0, N / 2);
		RD(N / 2, N / 2, N / 2);
		Result[idx] = '\0';
		cout << Result << endl;
	}
    return 0;
}

namnamseo 8년 전 1

1) N이 2 이상이고 모든 숫자가 같을 때의 경우 0 또는 1이 출력되어야 하는데 바로 LU를 호출하셔서, 이 경우의 처리가 불가능합니다.
2) Result 배열의 크기가 너무 작습니다. 0과 1이 반복되는 최악의 경우 500자를 훌쩍 넘어갑니다.

이 두 가지가 문제였던 것 같네요.
몇 가지 제안을 드리자면

1) LU, RU, LD, RD 모두 결국은 똑같은 일을 하는 함수이기 때문에, 밑의 소스처럼 함수를 통일하고, 4개로 쪼개야 할때만 쪼개도록 처리해주시면 훨씬 간단합니다.

2) Result 배열의 내용을 어차피 순서대로 출력할 것이기 때문에, 그때그때 cout<<'0';,cout<<'('; 처럼 처리하셔도 상관이 없습니다. 그렇게 하면 Result 배열의 크기를 미리 생각할 필요가 없습니다.

제가 소스에서 고친 부분을 첨부합니다.

// result 배열 크기
char Result[500] = { 0, };

// 함수 통일
void work(int Y, int X, int k) {
    int cnt0, cnt1, flag;
    cnt0 = 0; cnt1 = 0; flag = 0;
    if (k % 2 == 0) {
        for (int i = Y; i < Y + k; i++) {
            for (int j = X; j < X + k; j++) {
                if (Data[i][j] == '0') cnt0++;
                else if (Data[i][j] == '1') cnt1++;
                if (cnt0 != 0 && cnt1 != 0) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) {
                // 쪼개야 할 부분에서 괄호를 붙여주면 됨
                Result[idx++] = '(';
                work(Y, X, k / 2);
                work(Y, X + k / 2, k / 2);
                work(Y + k / 2, X, k / 2);
                work(Y + k / 2, X + k / 2, k / 2);
                Result[idx++] = ')';
                break;
            }
        }
        if (flag == 0) {
            if (cnt0 == (k*k)) Result[idx++] = '0';
            else Result[idx++] = '1';
        }
    }
    else {
        if (Data[Y][X] == '0') Result[idx++] = '0';
        else if (Data[Y][X] == '1') Result[idx++] = '1';
    }
    Result[idx++] = ')';
}

// main 함수
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Data[i];
    work(0, 0, N); // 한 줄ㄹ로 처리!
    //Result[idx] = '\0';  Result는 전역변수이므로 항상 0으로 초기화되어있음. ('\0' 과 같은 값)
    cout << Result << endl;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

쿼드트리 문제점을 찾지 못하겠습니다.

oin0107 8년 전 0

namnamseo 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말