박테리아 도와주세요.

  • fractize
    fractize

    박테리아 문제를 푸는데 시간 초과가 나옵니다.

    평가에 사용되는 테스트 케이스를 한번 보고싶은 마음이 굴뚝같네요.

    제가 만든 로직은 아래와 같습니다.

    여기서 더 최적화 할 여지가 있는지 조언을 구하고 싶습니다.

    두개의 버퍼를 마련합니다.

    하나는 입력 버퍼

    하나는 이전 버퍼입니다.

    네개의 이웃에 대한 링크 포인터를 가지는 Cell이라는 구조체를

    *문자가 있을때 마다 생성합니다.

    입력 버퍼와 이전 버퍼를 비교해서

    상하 좌우에 있는 이웃들과 Cell들을 연결짓습니다.

    여기까지 하면 Cell들로 이루어진 Dish가 완성됩니다.

    완성된 Dish에서

    이웃이 2개가 아닌 Cell들을 죽입니다.

    이것을 반복하면서 카운트를 셉니다.

    이웃이 2개인 Cell들만 남으면 -1을 반환하고

    Cell들이 모두 죽으면 카운트를 반환하고 종료합니다.

    #include <iostream>
    #include <set>
    #include <list>
    #include <memory.h>
    #include <stdio.h>
    #include <algorithm>
    
    using namespace std;
    
    class Dish;
    class Cell;
    
    class Dish {
    private:
        list<Cell*> cells;
    
    public:
        void insertCell(Cell*);
        int processResult();
    
    };
    
    class Cell {
    private:
       set<Cell*> neighbors;
    
    public:
    
        void destroy();
        void noticeDeath(Cell*);
        void connectWithNeighbor(Cell*);
        int getNCnt();
    };
    
    void Cell::destroy() {
        for (set<Cell*>::iterator itr = neighbors.begin(); itr != neighbors.end(); itr++) {
            (*itr)->noticeDeath(this);
        }
    }
    
    int Dish::processResult() {
        int result = 0;
        list<Cell*> detonate;
        unsigned int stable;
        while (cells.size() > 0) {
            stable = 0;
            for (list<Cell*>::iterator itr = cells.begin(); itr != cells.end(); itr++) {
                Cell* cell = *itr;
                if (cell->getNCnt() != 2) {
                    detonate.push_back(cell);
                } else {
                    stable++;
                }
            }
    
            if (cells.size() != 0 && cells.size() == stable) {
                return -1;
            }
    
            for (list<Cell*>::iterator ditr = detonate.begin(); ditr != detonate.end(); ditr++) {
                Cell *cell = *ditr;
                cell->destroy();
                list<Cell*>::iterator i = find(cells.begin(), cells.end(), cell);
                cells.erase(i);
                //delete cell;
            }
    
            detonate.clear();
    
            result++;
        }
        return result;
    }
    
    void Dish::insertCell(Cell* cell) {
        cells.push_back(cell);
    }
    
    
    
    void Cell::noticeDeath(Cell* cell) {
        neighbors.erase(cell);
    }
    
    void Cell::connectWithNeighbor(Cell* cell) {
        cell->neighbors.insert(this);
        neighbors.insert(cell);
    }
    
    int Cell::getNCnt() {
        return neighbors.size();
    }
    
    int main()
    {
        int caseSize = 0;
        int w;
        int h;
        char inputChar[2000];
        Cell *prevBuffer[2000];
        Cell *inputBuffer[2000];
        Cell *prevCell;
        Cell *cell;
    
        cin >> caseSize;
    
        for (int caseCnt = 0; caseCnt < caseSize; caseCnt++) {
            cin >> w;
            cin >> h;
    
            Dish dish;
    fgets(inputChar, 3, stdin);
            memset(prevBuffer, 0x00, sizeof(Cell*) * w);
            for (int hCnt = 0; hCnt < h; hCnt++) {
                memset(inputBuffer, 0x00, sizeof(Cell*) * w);
                //cin >> inputChar;
                fgets(inputChar, 1024, stdin);
                prevCell = 0x00;
                for (int wCnt = 0; wCnt < w; wCnt++) {
                    if (inputChar[wCnt] == '*') {
                        cell = new Cell();
                        dish.insertCell(cell);
                        inputBuffer[wCnt] = cell;
                        if (prevBuffer[wCnt] != 0x00) {
                            cell->connectWithNeighbor(prevBuffer[wCnt]);
                        }
                        if (prevCell != 0x00) {
                            cell->connectWithNeighbor(prevCell);
                        }
                    } else {
                        cell = 0x00;
                    }
                    prevCell = cell;
                }
                memcpy(prevBuffer, inputBuffer, sizeof(Cell*) * w);
            }
    
            cout << dish.processResult() << endl;
        }
    }
    


    12년 전
3개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    입력 데이터를 받아서 가공하는 부분도 new가 많아서 느리지만, 일단 processResult가 느립니다.

    매 순간마다 모든 cell을 확인하시는데, 굳이 모든 cell을 매번 다 봐줄 필요는 없죠. 이전 상태와 뭔가 바뀐 게 있는 cell들만 확인하도록 알고리즘을 바꾸셔야 할겁니다. time complexity가 O(h*w) 이내가 되도록 하셨는데도 시간초과가 난다면 new를 많이 한 것이 원인일 수 있겠습니다.


    12년 전 link
  • fractize
    fractize

    그냥 배열로 해버리고 거기서 꺼내 쓰도록 해야겠네요. ㅎㅎ 감사합니다.


    12년 전 link
  • kcm1700
    kcm1700

    스포일러가 담겨있어요.

    배열로 바꾸는 것만으로도 상당히 속도를 올릴 수는 있지만 아마 그걸로는 통과가 안될거예요. 매 순간마다 지금 방식대로 모든 살아있는 셀을 본다면 processResult가 시간복잡도가 얼마나 될지 먼저 계산해보세요. 그리고 어떻게 해야 상태가 바뀐 셀만 볼 수 있을지 생각해보시고 이 경우에는 시간복잡도가 얼마나 되는지 계산해보세요.


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