글 읽기 - 맞는 코드와 시간초과 코드의 비교 : 시간초과의 원인이 무엇이라고 생각하나요?

pjkov0824 3년 전 0

두 코드의 차이점은

solve 함수에 있습니다.

중복을 확인하는 과정에서

시간초과 코드 : solve 함수에 길이가 500001 visit 배열을 선언하고 사용(58)

맞는 코드 : solve 함수에 배열 대신 set을 선언하고 사용(183)

어느 부분에서 시간초과를 유발하는 것일까요?

visit이 스택이 받아들이기에는 너무 큰 것일까요? 그렇다면 왜 런타임 에러가 아니라 시간초과가 나오나요?

알려주시면 감사하겠습니다.

/*
시간 초과 코드
*/

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

int ans[1000][1000];
int sector[1000][1000];
char map[1000][1000];
int visit[1000][1000];
int lens[500001];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int N, M;

void BFS(int x, int y, int flag)
{
    queue<pair<int,int>> q;
    q.push(make_pair(y,x));
    visit[y][x] = 1;
    sector[y][x] = flag;
    int len = 1;

    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < M && yy >=0 && yy < N)
            {
                if (visit[yy][xx] == 0 && map[yy][xx] == '0')
                {
                    visit[yy][xx] = 1;
                    sector[yy][xx] = flag;
                    len++;
                    q.push(make_pair(yy,xx));
                }
            }
            
        }
    }
    lens[flag] = len;
}

void Solve(int x, int y)
{
    bool visit[500001] = {0,};
    for(int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >=0 && xx < M && yy >=0 && yy < N)
        {
            if (map[yy][xx] == '0' && visit[sector[yy][xx]] == 0)
            {
                visit[sector[yy][xx]] = 1;
                ans[y][x] += lens[sector[yy][xx]];
            }
        }
    }
    ans[y][x]++;
    ans[y][x] %= 10;
}

int main()
{
    cin >> N >> M;

    char * str = new char[M+1];

    for(int i = 0; i < N; i++)
    {
        scanf("%s", str);
        for(int j = 0; j < M; j++)
        {
            map[i][j] = str[j];
        }
    }

    int flag = 1;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == '0' && visit[i][j] == 0)
            {
                BFS(j, i, flag);
                flag++;
            }
        }
    }

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == '1')
            {
                Solve(j,i);
            }
        }
    }

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }
}

/*
통과 코드
*/
#include <iostream>
#include <queue>
#include <cstdio>
#include <set>

using namespace std;

int ans[1000][1000];
int sector[1000][1000];
char map[1000][1000];
int visit[1000][1000];
int lens[500001];

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int N, M;

void BFS(int x, int y, int flag)
{
    queue<pair<int,int>> q;
    q.push(make_pair(y,x));
    visit[y][x] = 1;
    sector[y][x] = flag;
    int len = 1;

    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < M && yy >=0 && yy < N)
            {
                if (visit[yy][xx] == 0 && map[yy][xx] == '0')
                {
                    visit[yy][xx] = 1;
                    sector[yy][xx] = flag;
                    len++;
                    q.push(make_pair(yy,xx));
                }
            }
            
        }
    }
    lens[flag] = len;
}

void Solve(int x, int y)
{
    //bool visit[500001] = {0,};
    set<int> s;
    for(int i = 0; i < 4; i++)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >=0 && xx < M && yy >=0 && yy < N)
        {
            if (map[yy][xx] == '0')
            {
                // visit[sector[yy][xx]] = 1;
                // ans[y][x] += lens[sector[yy][xx]];
                s.insert(sector[yy][xx]);
            }
        }
    }
    for(auto k : s)
    {
        ans[y][x] += lens[k];
    }
    ans[y][x]++;
    ans[y][x] %= 10;
}

int main()
{
    cin >> N >> M;

    char * str = new char[M+1];

    for(int i = 0; i < N; i++)
    {
        scanf("%s", str);
        for(int j = 0; j < M; j++)
        {
            map[i][j] = str[j];
        }
    }

    int flag = 1;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == '0' && visit[i][j] == 0)
            {
                BFS(j, i, flag);
                flag++;
            }
        }
    }

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == '1')
            {
                Solve(j,i);
            }
        }
    }

    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            printf("%d", ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

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

문제

문제

출처

ICPC

맞는 코드와 시간초과 코드의 비교 : 시간초과의 원인이 무엇이라고 생각하나요?

pjkov0824 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말