글 읽기 - 시간초과가 나는데 이유를 모르겠습니다.

songyw98 2년 전 0

아무리 생각해 봐도 멈추는 이유를 모르겠습니다. (62%에서 멈춥니다.)

루프를 많이 돌아서 그런 것 같아 최대한 막아봤는데도 잘 모르겠습니다.

루프를 많이 돌아서 생기는 문제인가요?

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

struct Index {
    int x;
    int y;
};

int MAP[300][300];
bool VISITED[300][300];
int H, W;
int result = 0;

deque<Index> queue;

void initialize() {
    cin >> H >> W;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> MAP[i][j];
            VISITED[i][j] = false;
        }
    }
}

void resetVisited() {
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++)
            VISITED[i][j] = false;
}

void bfs() {
    struct Index item = queue.front();
    queue.pop_front();
    struct Index index;

    if (MAP[item.y + 1][item.x] != 0 && VISITED[item.y + 1][item.x] == false) {
        index.x = item.x;
        index.y = item.y + 1;
        queue.push_back(index);
        VISITED[index.y][index.x] = true;
    }
    if (MAP[item.y][item.x + 1] != 0 && VISITED[item.y][item.x + 1] == false) {
        index.x = item.x + 1;
        index.y = item.y;
        queue.push_back(index);
        VISITED[index.y][index.x] = true;
    }
    if (MAP[item.y - 1][item.x] != 0 && VISITED[item.y - 1][item.x] == false) {
        index.x = item.x;
        index.y = item.y - 1;
        queue.push_back(index);
        VISITED[index.y][index.x] = true;
    }
    if (MAP[item.y][item.x - 1] != 0 && VISITED[item.y][item.x - 1] == false) {
        index.x = item.x - 1;
        index.y = item.y;
        queue.push_back(index);
        VISITED[index.y][index.x] = true;
    }
}

void counter() {
    for (int i = 1; i < H - 1; i++) {
        for (int j = 1; j < W - 1; j++) {
            if (MAP[i][j] != 0) {
                int count = 0;
            
                if (MAP[i + 1][j] == 0 && VISITED[i + 1][j] == false) count++;
                if (MAP[i][j + 1] == 0 && VISITED[i][j + 1] == false) count++;
                if (MAP[i - 1][j] == 0 && VISITED[i - 1][j] == false) count++;
                if (MAP[i][j - 1] == 0 && VISITED[i][j - 1] == false) count++;

                MAP[i][j] -= count;
                if (MAP[i][j] < 0) MAP[i][j] = 0;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    initialize();
    while (true) {
        int iterate = 0;

        for (int i = 1; i < H - 1; i++) {
            for (int j = 1; j < W - 1; j++) {
                if (VISITED[i][j] == false && MAP[i][j] != 0) {
                    struct Index check;
                    
                    check.x = j;
                    check.y = i;

                    queue.push_back(check);
                    while (true) {
                        bfs();
                        if (queue.empty() == true)
                            break;
                    }
                    iterate += 1;
                }
            }
        }

        if (iterate > 1)
            break;

        counter();
        result++;
        resetVisited();
    }

    cout << result << endl;

    return 0;
}

sungjaecho97 2년 전 2

해당 조건을 확인하지 않고 있습니다.

만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

iterate가 0인 경우를 처리해주면 됩니다.

songyw98 2년 전 0

감사합니다. 해결되었습니다.

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

문제

문제

출처

ICPC

시간초과가 나는데 이유를 모르겠습니다.

songyw98 2년 전 0

sungjaecho97 2년 전 2

songyw98 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말