글 읽기 - 시간 초과가 발생하는 이유를 알고 싶습니다 (주석 있음)

themion 3년 전 0

코드 자체는 별로 느린 것 같지 않은데, 86% 부근에서 시간 초과가 발생합니다.

while문을 사용하긴 했지만, 같은 노드를 여러 번 방문한다고 무한 루프를 도는 코드는 아니라고 생각합니다.

어디서 시간 초과가 발생하는 걸까요?

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> edge;

#define MAX_N 500
#define INF 0x3f3f3f3f
#define _cost first
#define _node second

// 방문 이력과 가장 마지막으로 방문한 노드, 소모한 총 비용을
// 클래스로 묶어서 사용
class router
{
public:
    vector<bool> visit;
    int cost = 0, last_visit;

    router(){}
    router(int n, int node) 
    {
        this->visit = vector<bool>(n, false); 
        this->visit[node] = true;
        this->last_visit = node;
    }
};

int N, M, W;
// 입력받은 에지 중 비용이 가장 작은 에지를 따로 저장
int m[MAX_N][MAX_N];

// v[i]: 시작점이 i인 에지의 집합
vector<edge> v[MAX_N];

void set_min(int &a, int b) { a = a < b ? a : b; }

bool find_cycle(int start)
{
    vector<int> cost(N, INF);
    cost[start] = 0;
    queue<router> routes;

    routes.push(router(N, start));

    while (!routes.empty())
    {
        router r = routes.front();
        routes.pop();

        // 사용 가능한 에지에 대해 탐색을 반복
        for (edge e : v[r.last_visit])
        {
            // r을 변형하면 안되므로 복사하여 사용
            router r_ = r;
            
            // 방문한 적이 있는 노드로 이동한다면 사이클이 만들어진다
            if (r_.visit[e._node] == true)
            {
                // 사이클을 만들어 기존 비용보다 적은 비용을 만든다면
                // 원하는 경우를 찾았으므로 true를 반환
                if (cost[e._node] > r_.cost + e._cost) 
                    return true;
                // 그렇지 않다면 r을 폐기
                else continue;
            }
            // 방문한 적 없는 노드이지만 방문하여 비용이 감소할 때
            // r을 갱신하여 routes에 push
            else if (cost[e._node] > r_.cost + e._cost)
            {
                r_.last_visit = e._node;
                r_.visit[e._node] = true;
                r_.cost += e._cost;

                cost[e._node] = r_.cost;

                routes.push(r_);
            }
        }
    }

    return false;
}

bool boj_1865()
{
    int a, b, c;

    scanf("%d %d %d", &N, &M, &W);

    // 전역변수 초기화
    for (int i = 0; i < N; i++) 
    {
        std::fill_n(m[i], N, INF);
        v[i] = vector<edge>();
    }
    
    // 각 에지를 입력받아 값이 가장 작은 것들만 사용
    for (int i = 0; i < M + W; i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        if (i >= M) c = -c;

        set_min(m[--a][--b], c);
        if (i < M) set_min(m[b][a], c);
    }

    // 입력받은 에지를 v에 보관
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) 
        if (m[i][j] != INF) v[i].push_back({m[i][j], j});

    // 각 노드를 시작점으로 하여 사이클을 발견할 수 있는지 확인
    for (int i = 0; i < N; i++) if (find_cycle(i)) return true;

    return false;
} 

int main()
{
    int TC;
    scanf("%d", &TC);

    while (TC--) printf("%s\n", boj_1865() ? "YES" : "NO");

    return 0;
} 

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

문제

문제

출처

ICPC

시간 초과가 발생하는 이유를 알고 싶습니다 (주석 있음)

themion 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말