boardcover2 시간초과

  • ckdhyeon95
    ckdhyeon95

    boardcover2 문제 시간초과를 해결하고자 질문드립니다.

    종만북을 참고하여

    1. block의 상대좌표 구하기
    2. vector unique를 통해 block 중복 제거
    3. block으로 map을 덮을 수 있는지 확인

      3.1 덮을 수 없다면 다음칸 확인
      3.2 덮을 수 있다면 map을 block으로 덮은 뒤 다음칸 확인, 덮지 않은 채 다음칸 확인 (모두 고려)

    4. 휴리스틱을 이용하여 가지치기

    위 개념을 바탕으로 접근하여 알고리즘을 구현하였습니다.
    하지만 시간초과가 납니다.

    세부적인 구현에서 차이가 나서 시간초과가 나는건지,
    혹은 제가 고려하지 못한 부분이 있는지 알고싶습니다.

    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <utility>
    #include <algorithm>
    
    using namespace std;
    
    char mapArr[10][10];
    char block[10][10];
    int inputH, inputW, inputR, inputC;     
    vector<vector<pair<int, int> > > coordinate(4);     //block의 상대좌표 vector
    int resultVal = -1;
    int bNum = 0;       //block size
    
    // 배열 돌리기 함수
    void rotateArr() {
    
        char tempArr[10][10];
    
        for (int i = 0; i < inputR; ++i) {
            for (int j = 0; j < inputC; ++j) {
                tempArr[j][i] = block[inputR - 1 - i][j];
            }
        }
    
        int temp = inputR;
        inputR = inputC;
        inputC = inputR;
        memcpy(block, tempArr, sizeof(block));
    }
    
    // block의 상대좌표 구하는 함수
    void getCoordinate() {
    
        for (int i = 0; i < 4; ++i) {
    
            int firstR = -1;
            int firstC = -1;
            for (int j = 0; j < inputR * inputC; ++j) {
                int nowR = j / inputC;
                int nowC = j % inputC;
                if (block[nowR][nowC] != '#')
                    continue;
    
                if (firstR == -1 && firstC == -1) {
                    firstR = nowR;
                    firstC = nowC;
                }
    
                coordinate[i].push_back(make_pair(nowR - firstR, nowC - firstC));
            }
    
            rotateArr();
        }
    
    }
    
    // block을 놓을 수 있는지 확인하는 함수
    bool isPossible(int nowR, int nowC, int type) {
    
        bool check = true;
        for (int i = 0; i < coordinate[type].size(); ++i) {
    
            int nextR = nowR + coordinate[type][i].first;
            int nextC = nowC + coordinate[type][i].second;
    
            if (nextR < 0 || nextR >= inputH || nextC < 0 || nextC >= inputW) {
                check = false;
                break;
            }
    
            if (mapArr[nextR][nextC] != '.') {
                check = false;
                break;
            }
    
        }
    
        return check;
    }
    
    //mapArr에 block을 넣는 함수
    void writeMap(int nowR, int nowC, int type) {
    
        for (int i = 0; i < coordinate[type].size(); ++i) {
    
            int nextR = nowR + coordinate[type][i].first;
            int nextC = nowC + coordinate[type][i].second;
    
            mapArr[nextR][nextC] = 'a';
    
        }
    
    }
    
    void solve(int pos, int cnt) {
    
        int nowR = -1;
        int nowC = -1;
        int space = 0;
    
        for (int i = pos; i < inputH * inputW; ++i) {
    
            int tempR = i / inputW;
            int tempC = i % inputW;
    
            if (mapArr[tempR][tempC] == '.') {
                space += 1;
                if (nowR == -1 && nowC == -1) {
                    nowR = tempR;
                    nowC = tempC;
                }
            }
    
        }
    
        int heuristic = space / bNum;
    
        if (cnt + heuristic <= resultVal)
            return;         // 가지치기
    
        if (nowR == -1 && nowC == -1) {
            resultVal = max(resultVal, cnt);
            return;
        }
    
        int ret = 0;
    
        char backup[10][10];    //mapArr 백업을 위한 배열
    
        //현재 좌표(nowR, nowC)를 시작점으로 삼는 경우
        for (int type = 0; type < coordinate.size(); ++type) {
    
            if (!isPossible(nowR, nowC, type))
                continue;
            memcpy(backup, mapArr, sizeof(backup)); //백업한뒤
            writeMap(nowR, nowC, type);             //mapArr에 block넣고
            solve(pos + 1, cnt + 1);                //재귀호출
            memcpy(mapArr, backup, sizeof(mapArr)); //mapArr 복원
    
        }
        //현재 좌표(nowR, nowC)를 건너뛰는 경우
        solve(pos + 1, cnt);
    
    
    }
    
    int main() {
    
        int testCase;
        cin >> testCase;
        while (testCase-- > 0) {
    
            //초기화
            bNum = 0;
            resultVal = -1;
            memset(mapArr, 0, sizeof(mapArr));
            memset(block, 0, sizeof(block));
            coordinate = vector<vector<pair<int, int> > >(4);
            cin >> inputH >> inputW >> inputR >> inputC;
            for (int i = 0; i < inputH; ++i) {
                for (int j = 0; j < inputW; ++j)
                    cin >> mapArr[i][j];
            }
            for (int i = 0; i < inputR; ++i) {
                for (int j = 0; j < inputC; ++j) {
                    cin >> block[i][j];
                    if (block[i][j] == '#')
                        bNum += 1;
                }
            }
    
            //우선 block의 상대좌표 구한 뒤
            getCoordinate();
            // 중복제거 후
            sort(coordinate.begin(), coordinate.end());
            coordinate.erase(unique(coordinate.begin(), coordinate.end()), coordinate.end());
            // solve함수 호출
            solve(0, 0);
    
            cout << resultVal << '\n';
    
        }
    
        return 0;
    }
    

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