BOARDCOVER문제를 풀었는데, 코드가 너무 느리게 돕니다. 왜그런지 이유를 알고 싶습니다.

  • boxlug
    boxlug

    일단 저는 현재 일명 종만북이라고 불리우는 구종만씨가 저술하신 알고리즘 문제해결 전략이라는 책을 보면서 이제 갓 프로그래밍 대회를 준비하기 시작한 정말 생초짜입니다. 그래서 이 질문이 너무 초보적인 질문이라서 다른분들의 눈살이 찌푸려 지실수도 있겠지만, 그럼에도 불구하고 저로서는 도저히 답을 찾을수가 없어서 이렇게 질문드립니다.
    제가 풀고있는 문제는 바로 이 문제입니다.
    BOARDCOVER
    저한테는 쉽지 않게 느껴지는 문제지만, 여기 계신분들한테는 아마 너무나도 쉽게 느껴지실거라 생각됩니다.
    책에서도 단순한 재귀호출을 통해서 완전탐색을 이용하여 해결할 수 있다고 하고 있고, 저 또한 그렇게 생각하여 완전탐색으로 문제를 해결해 보려했습니다. 그런데 어째서인지 답을 구하는데 정말 오랜시간이 걸립니다. 초보의 눈으로 보기에는 별 다른 것이 없어 보이는데, 정답 코드는 2초안에 돌아야 하는 코드인데 저는 2초를 넘어서 2시간 가까이 걸리는 것 같습니다. 그런데 저혼자서는 아무리 봐도 방법이 없어 이렇게 질문을 드립니다.
    아래에 저의 소스코드를 첨부하겠습니다.

    #include<iostream>

using namespace std;

int testNum, lineNum, colNum;
bool** taken;

int dy[8] = { 0, -1, 0, 1, -1, 0, 1, 0 };
int dx[8] = { -1, 0, -1, 0, 0, 1, 0, 1 };



int countCovers(bool** taken, int x, int y);


int main(void) {
    cin >> testNum;

    char** board;

    for (int i = 0; i<testNum; i++) {
        cin >> lineNum;
        cin >> colNum;

        //board dynamic allocating
        board = new char*[lineNum];
        for (int j = 0; j<lineNum; j++)
            board[j] = new char[colNum + 1];

        //board initializing
        for (int j = 0; j<lineNum; j++) {
            cin.ignore();
            cin >> board[j];
        }

        //taken dynamic allocating
        taken = new bool*[lineNum];
        for (int j = 0; j<lineNum; j++)
            taken[j] = new bool[colNum];

        //taken initializing
        for (int j = 0; j<lineNum; j++)
            for (int k = 0; k<colNum; k++) {
                if (board[j][k] == '#')
                    taken[j][k] = true;
                else
                    taken[j][k] = false;
            }

        //print output
        cout << countCovers(taken, 0, 0) << endl;

        //free board
        for (int j = 0; j<lineNum; j++)
            delete board[j];
        delete board;

        //free taken
        for (int j = 0; j<lineNum; j++)
            delete taken[j];
        delete taken;
    }

    return 0;
}

int countCovers(bool** taken, int x, int y) {


    bool finished = true;
    int ret = 0;

    //check finished
    for (int i = x; i<lineNum; i++)
        for (int j = (i==x)? y : 0 ; j<colNum; j++)
            if (!taken[i][j]) {
                finished = false;
                break;
            }

    //if taken is fully occupied return 1, else if is not fully occupied return 0
    if (finished) {
        for (int i = 0; i<lineNum; i++)
            for (int j = 0; j<colNum; j++)
                if (!taken[i][j])
                    return 0;

        return 1;
    }

    //cout << "return sector finished\n";

    //calculate ret
    for (int i = x; i<lineNum; i++)
        for (int j = (i==x) ? y: 0; j<colNum; j++)
            if (!taken[i][j]) {
                taken[i][j] = true;
                for (int k = 0; k<4; k++) {
                    if (i == 0 && ((k == 0) || (k == 1)))
                        continue;
                    if (j == 0 && ((k == 0) || (k == 2)) )
                        continue;
                    if (j == colNum - 1 && ((k == 1) || (k == 3)) )
                        continue;
                    if (i == lineNum - 1 && ((k == 2) || (k == 3)))
                        continue;

                    if (!taken[i + dx[k * 2]][j + dy[k * 2]] && !taken[i + dx[k * 2 + 1]][j + dy[k * 2 + 1]]) {
                        taken[i + dx[k * 2]][j + dy[k * 2]] = taken[i + dx[k * 2 + 1]][j + dy[k * 2 + 1]] = true;
                        ret += countCovers(taken, i, j);
                        taken[i + dx[k * 2]][j + dy[k * 2]] = taken[i + dx[k * 2 + 1]][j + dy[k * 2 + 1]] = false;
                    }
                }
                taken[i][j] = false;
            }

    return ret;
}

    위의 소스코드에 대해서 설명을 드리자면 일단 전역 변수인 testNum, lineNum, colNum은 각각 이름에서 알수 있듯이 테스트의 수, 라인의 수, 열의 수를 저장하기 위한 변수입니다. 전역변수인 더블 포인터 taken은 이름이 좀 부적절할 수 있지만, 해당 좌표가 덮여있는지 여부를 나타내는 2차원 배열을 가리키기 위한 변수입니다. 일단 main에서는 전역변수에 값을 입력받고, 적절히 초기화 해준뒤에 countCovers라는 함수를 호출하여 이 결과를 다시 출력해주는 작업만을 수행합니다.
    countCovers함수에는 3개의 매개변수가 있는데, taken은 아까 말한 해당 좌표가 덮여있는지 여부를 나타내기 위한 taken을 넘겨주고 접근하기 위한 매개변수이고, x와 y는 각각 2차원 배열에서의 행과 열을 나타냅니다.

    그리고, finished라는 bool변수가 있는데 이는 보드를 덮는 작업이 끝났는지(가득 채우는데에 성공했든 못했든)를 나타내는 bool변수입니다. 끝났는지 여부의 판단은 현재 x와 y의 위치부터해서 배열의 끝까지가 모두 가득차있으면 끝났다고 판단하고, finished가 true일 때만 다시 2차원 배열 전체를 검사하여 가득차있으면 1을 리턴하고 빈부분이 있다면 0을 리턴하도록 했습니다.
    그리고 밑에서 재귀적으로 실제 리턴할 값인 ret를 계산하는 부분은 책에서는 약간 다르게 현재 좌표를 기준으로 남은 블록이나 좌표들이 뒤에 나타낼때에 대해서로 가정하고 하셨는데, 저는 현재 좌표를 기준으로 상하좌우에 넣어보는 것으로 구현햇습니다.
    그에 대한 상대좌표 값은 dx와 dy라는 배열에 저장했습니다. 그리고 안쪽 for문의 k라는 변수는 이런 상대 좌표들을 지정해주기 위한 변수입니다. 앞의 여러개의 if문들은 이렇게 상대 좌표로 나타내려고 할때 가장자리 좌표 값에서 빼거나 더하는 등의 연산을 했을때, 배열의 주소에서 벗어나는 것에 대한 예외처리를 해주기 위해서 구현했습니다.
    이중 for문안에서 현재 진행중인 좌표가 비어있을때(false일 때에만 안의 for문을 이용하여 상하좌우에 2개의 블록을 넣을수 있는지 여부를 검사했으며, 넣을 수 있다고 판단되면, 해당 좌표값들 역시 true로 바꿔준뒤, 다시 재귀호출을 통해서 자기 자신을 호출하도록 했습니다.

    여기까지가 대략적인 코드 설명인데, 아무래도 제가 코딩경험이 많지 않다보니 코드역시 더럽고 비효율적인것 같습니다ㅠㅠ
    저자 분이 구현하신 것보다 느린건 당연할지도 모르겠지만, 이정도로 많이 차이가 난다는 것은 뭔가 다른 차원의 심각한 문제인 것 같기도 하고, 이번기회에 뭐가 문제인지 확실히 알아둬야 할 것 같아서 이렇게 질문을 남깁니다.
    이런 질문을 드리는것이 너무 염치 없을지 모르지만, 그래도 부탁드립니다.
    혹시나 코드에서 모호하거나 이상하다 싶은게 있으면, 댓글달아주시면 다시 답변을 통해서 보충 설명 하도록 하겠습니다.
    제발 도와주세요ㅠㅠ


    6년 전
2개의 댓글이 있습니다.
  • seico75
    seico75

    글로 다 설명하기는 좀 어렵지만...
    일단 직접 작성하신 코드는 countCovers 에서 하는 일은
    1. 종료 조건인지 확인
    2. 모든 빈칸에 대해서 각 조합이 가능한지를 확인하고
    가능하면 매꾸고, 그상황에서 나머지가 가능한지 재귀
    (한번의 콜에서 모든 빈칸에 대한 모든 조합을 찾음)

    종만북의 해법은
    1. 가장 처음 나타난 빈칸을 찾고 (그러면서 종료 조건 확인)
    2. 그 빈칸에 대해서 가능한 조합들을 찾아 재귀
    (한번의 콜에 하나의 빈칸에 대한 모든 조합을 찾음)

    구분이 되시나요?

    #######
#..#..#
#.###.#
#######

    이런 지도에서 작성하신 코드는
    첫콜에서 왼쪽을 선택(depth0)하고 재귀 호출해서 오른쪽(depth1)찾고
    다시 오른쪽을 선택(depth0)하고 재귀호출에서 종료(depth1)
    종만북은
    첫콜에서 왼쪽선택(depth0)하고 재귀호출에서 오른쪽(depth1) 찾고 다시 재귀해서 종료(depth2)
    depth를 떠나서 선택하는 횟수가 3, 2로 차이가 나죠.
    선택하는 조합의 수는 2 vs 1. ( 2 * 1 vs 1 * 1
    (답도 2, 1로 차이가 날꺼 같네요)
    선택가능한 블럭이 3개라면
    3 * 2 * 1 vs 1 * 1 * 1 ....
    복잡할수록 확인하는 조합의 수가 훅 늘어나서 느려질 겁니다.

    사족으로...

    • 한점이 주어질 때 패턴확인하는 방법이 틀린 것은 아니지만 책의 방법이 주어진 점 이전에는 모든 점들이 다 차 있다는 가정을 할 수 있어서 편리한 점이 있습니다. 선택하신 방법으로 하려면 한번 선택을 성공했으면 재귀만하고 루프를 나가야 할 것 같습니다.

    • 맵의 크기가 제한되어 있기 떄문에 동적으로 할당하지 말고 최대크기 배열로 잡는 것이 수월할 것 같습니다. 동적할당을 해야한다면 board 와 taken 을 한 루프에서 할당하는 것이 좋을 것 같고. taken 과 board 는 동일한 정보를 가지고 있어서 두개를 분리할 필요가 없어 보입니다. (비었는지 찼는지.. true/false #/. 의 차이만.. )

    긴 설명글 쓰시느라고 고생하셨는데 명쾌한 설명이 안된 것 같아서 죄송하네요. 직접 그려서 설명을 드리면 좋을텐데...


    6년 전 link
  • boxlug
    boxlug

    아 죄송합니다 ㅠㅠ 보기는 봤었는데, 개인사정때문에 이래저래 못보다가 이제야 여유가 되서 보게되었습니다. 친절한 설명 정말 감사드립니다. 덕분에 고민이 해결된 것 같습니다. 설명을 잘해주셔서 직접 그려서 안해주셔도 될 정도입니다. 정말 감사드립니다.


    6년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.