글 읽기 - 시간초과...뭐가 문제인가요?

gs21122 2년 전 0

코드 열심히 짰는데 시간초과 떠서 조금 짜증나네요,,

44%에서 시간초과 나는데 어디서 시간초과가 나는건가요..?..

#include <bits/stdc++.h>
using namespace std;

int m,n;
int tomato[1001][1001];
queue <pair<pair<int, int>, int>> q;

bool is_full()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        if(tomato[i][j]==0)
            return false;
    return true;
}

bool check(int x, int y)
{
    if(x<1||y<1||x>n||y>m||!tomato[x][y]==0)
        return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>m>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>tomato[i][j];
    if(is_full())
    {
        cout<<0;
        return 0;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(tomato[i][j]==1) q.push({{i,j},0});
    while(!q.empty())
    {
        int day=q.front().second;
        int x=q.front().first.first;
        int y=q.front().first.second;
        q.pop();
        if(check(x+1, y)) q.push({{x+1, y}, day+1}), tomato[x+1][y]=1;
        if(check(x-1, y)) q.push({{x-1, y}, day+1}), tomato[x-1][y]=1;
        if(check(x, y+1)) q.push({{x, y+1}, day+1}), tomato[x][y+1]=1;
        if(check(x, y-1)) q.push({{x, y-1}, day+1}), tomato[x][y-1]=1;

        if(is_full())
        {
            cout<<day+1;
            return 0;
        }
    }

    if(!is_full())
        cout<<-1;
}

djm03178 2년 전 1

토마토가 모두 익는 데에 걸리는 시간은 최대 O(NM)일입니다. 그때마다 is_full을 호출하는데 이 체크 시간 역시 O(NM)이므로 총 O((NM)^2) 시간이 걸리게 됩니다.

gs21122 2년 전 0

@djm03178 감사합니다

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

문제

문제

출처

ICPC

시간초과...뭐가 문제인가요?

gs21122 2년 전 0

djm03178 2년 전 1

gs21122 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말