박테리아 문제 오답 케이스가 뭘까요?;;;

  • coldradio
    coldradio

    계속 시간 초과가 뜨다가 이번에는 오답 행진을 하고 있습니다.
    머리가 멍해질 때까지 생각해 봤는데, 잘 모르겠네요.
    고수님의 도움을 요청드려요.
    간단한 알고리즘 설명입니다.

    1. 1초 후를 시뮬레이션 합니다. tick()함수.
    2. delete_path_and_return_len()을 for loop으로 돌립니다. 이 함수는 패스를 찾아서 그 길이를 돌려줍니다. 대상이 된 path는 지워주고요. 여기서 약간의 트릭을 썼는데, path를 찾을 때, 처음 부터 찾는게 아니라, 이전 찾아진 path 시작점부터 찾았습니다. 처음부터 찾을라니 시간초과가 뜨더라구요;;

    3. delete_path_and_return_len()이 path를 더 이상 찾지 못하면, 박테리아가 하나도 없는지 봅니다. empty()함수.

    4. 비어 있지 않다면, loop이 있다는 말이므로 -1 출력. 아니면 (max_len+1) / 2 +1

    몇가지 덧붙이면

    • 인텍싱은 (1,1)부터 했습니다. 편의를 위해
    • 예외처리한 경우는, 초기에 박테리아 하나도 없는 경우.

    알고리즘이 틀린 걸까요? 아니면 구현을 잘 못한걸까요?;;
    아래는 소스입니다.

    #include <iostream>
    #include <vector>
    #include <cstring>
    using namespace std;
    
    int T, W, H, last_h, last_w;
    char B[505][505];
    
    void tick() {
        std::vector<std::pair<int, int> > ch;
    
        for (int h = 1; h <= H; h++)
            for (int w = 1; w <= W; w++)
                if (B[h][w] && (B[h - 1][w] + B[h + 1][w] + B[h][w - 1] + B[h][w + 1]) != 2)
                    ch.push_back(std::make_pair(h, w));
        for (size_t i = 0; i < ch.size(); i++)
            B[ch[i].first][ch[i].second] = 0;
    }
    
    int delete_path_return_len() {
        int h, w, fnd = 0;
        //path 시작점을 찾는다.
        for (h = last_h; h <= H; h++) {
            for (w = last_w; w <= W; w++) {
                // 박테리아를 가지고 있고, 주변 박테리아가 1개보다 같거나 작을 때, 나는 path 시작점이 된다.
                if (B[h][w] && (B[h - 1][w] + B[h + 1][w] + B[h][w - 1] + B[h][w + 1]) <= 1) {
                    fnd = 1;
                    break;
                }
            }
            if (fnd) break;
        }
    
        if (!fnd) return 0;
    
        int l = 0;
        // 찾은 path 시작점을 저장하고 다음에는 여기서 시작한다. 이 시점 이전에는 path 시작점이 있을 수 없으므로
        last_h = h, last_w = w;
    
        // path를 따라가며 길이를 구하고 지운다.
        while (B[h][w]) {
            l++;
            B[h][w] = 0;
            if (B[h - 1][w]) h--;
            else if (B[h + 1][w]) h++;
            else if (B[h][w - 1]) w--;
            else if (B[h][w + 1]) w++;
        }
        return l;
    }
    
    int empty() {
        for (int h = 1; h <= H; h++)
            for (int w = 1; w <= W; w++)
                if (B[h][w])
                    return 0;
        return 1;
    }
    
    int main() {
        cin >> T;
        while (T--) {
            memset(B, 0, sizeof(B));
            cin >> W >> H;
            last_h = last_w = 1;
            for (int h = 1; h <= H; h++) {
                cin >> &B[h][1];
                for (int w = 1; w <= W; w++)
                    B[h][w] = (B[h][w] == '*');
            }
            if (empty())
                cout << "0" << endl;
            else {
                tick();
                int mx = 0;
                for (int i = delete_path_return_len(); i; i = delete_path_return_len()) {
                    mx = max(mx, i);
                }
                cout << (empty() ? (mx + 1) / 2 + 1 : -1) << endl;
            }
        }
    }
    


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

    알고리즘은 틀리지 않았는데, 구현에 오류가 있습니다. 조금만 코드를 손보면 정답 판정을 받으실 겁니다.

    1
    6 2
    ...***
    ***...

    를 입력으로 넣어보세요.


    6년 전 link
  • coldradio
    coldradio

    아. 감사합니다.
    거기에 문제가 있는지 생각도 못했네요 ^^
    많이 배웠습니다!


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