글 읽기 - 50% 시간초과 최적알고리즘같은데.. 고수님들 도와주세요

hyj2508 4년 전 0

말그대로 최적알고리즘 같은데 50%에서 시간초과가 뜨네요 ㅠㅠ

pair 로 받아서 bfs 를 통해 연결요소 개수를 세는 방식으로 구현했는데,

어느부분에서 시간초과가 나는걸까요?

v.size()도 3000 미만이라 그렇게 많이 돌지 않을것 같은데..

도움부탁드립니다 고수님들 ㅜㅜ

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
queue<pair<int, int>> q;
vector<pair<int, int>> v;

int arr[5001][5001];
int visited[5001][5001];

int bfs(pair<int, int> start){
    while(!q.empty()) q.pop();
    memset(visited, 0, sizeof(visited));
    q.push(start);
    int startx = start.first;
    int starty = start.second;
    visited[startx][starty] = 1;
    while(!q.empty()){
        pair<int, int> front = q.front();
        int frontx = front.first;
        int fronty = front.second;
        q.pop();
        for(int i=0;i<v.size();i++){
            int tx = v[i].first;
            int ty = v[i].second;
            if(visited[tx][ty]==0 && arr[tx][ty]!=0 && \
               ((frontx-tx)*(frontx-tx)+(fronty-ty)*(fronty-ty) \
               <=(arr[frontx][fronty]+arr[tx][ty])*(arr[frontx][fronty]+arr[tx][ty]))) {
                visited[tx][ty] = 1;
                q.push(make_pair(tx,ty));
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    // freopen("input.txt","r", stdin);
    int num;
    cin >> num;
    for(int i=0;i<num;i++){
        int ans = 0;
        int n, p, q, r;
        cin>>n;
        v.clear();
        for(int i=0;i<n;i++){
            cin>>p>>q>>r;
            arr[p][q] = r;
            v.push_back(make_pair(p,q));
        }
        for(int i=0;i<v.size();i++){
            int tx = v[i].first;
            int ty = v[i].second;
            if(arr[tx][ty]!=0 && visited[tx][ty]==0){
                ans++;
                bfs(make_pair(tx,ty));
            }
        }
        cout<<ans<<'\n';

    }
    return 0;
}

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

문제

문제

출처

ICPC

50% 시간초과 최적알고리즘같은데.. 고수님들 도와주세요

hyj2508 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말