글 읽기 - 왜 시간이 오래 걸릴까요

cyc1119 3년 전 1

문명 문제를 풀고 있는데, 시간 초과가 떴습니다. 이 코드를 먼저 설명하자면 bfs 와 union find를 응용한 코드 입니다. Q에서 사용한 struct인 p는 어떤 좌표(x,y)에 어떤색깔 z를 세계의 시간이 t일때 칠하겠다는 것입니다. 이를 통해 색깔을 칠하면서 바로 상하좌우를 보면서 문병이 결합되었는지 체크합니다. 그리고 union find를 하면서 시간이 줄어들도록 경로압축도 했습니다. 프로그램의 예제는 잘 나옵니다.

2000 10 1355 934 1935 436 934 1249 435 1253 1423 1953 45 1054 1395 1943 943 4 642 23 643 124

그러나 질문검색에 있는 위의 예제를 넣어보니 나오지 않는것을 보면 제 코드의 문제가 확실히 있는것 같은데 저는 잘 모르겠습니다. 대부분 시간 초과각 났을 때 질문을 하시던데, 저는 아예돌아가지도 않는 코드로 질문하여서 죄송합니다.

#include <bits/stdc++.h>
using namespace std;
int world[2001][2001], node[100001], worldtime=-1;
int n,k,cnt,dx[]={0,1,0,-1}, dy[]={1,0,-1,0};
typedef struct point
{
    int x,y,z,t;
}p;
int highnode(int x)
{
    if(node[x]==x) return x;
    else return node[x]=highnode(node[x]);
}
bool safe(int x,int y)
{
    return ((1<=x && x<=n) &&(1<=y && y<=n));
}
int main()
{
    scanf("%d %d",&n,&k);
    queue<p> Q;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        node[i]=i;
        Q.push({x,y,i,0});
    }
    while((cnt+1)<k)
    {
        worldtime++;
        while(!Q.empty())
        {
            if(Q.front().t>worldtime) break;
            p v=Q.front(); Q.pop();
            world[v.x][v.y]=v.z;
            for(int i=0;i<4;i++)
            {
                int x=v.x+dx[i], y=v.y+dy[i];
                if(!safe(x,y)) continue;
                if(world[x][y]==0) Q.push({x,y,v.z,v.t+1});
                else if(highnode(world[x][y])==highnode(world[v.x][v.y])) continue;
                else
                {
                    cnt++;
                    int p=highnode(world[v.x][v.y]), u=highnode(world[x][y]);
                    if(p<u) swap(p,u);
                    node[p]=u;
                }
            }
        }
    }
    cout<<worldtime;
    return 0;
}

cyc1119 3년 전 0

아 체크한점의 중복체크를 막았더니 됬네요

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

문제

문제

출처

ICPC

왜 시간이 오래 걸릴까요

cyc1119 3년 전 1

cyc1119 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말