글 읽기 - struct, pair 차이에 따른 "시간 초과" 질문

cejung 1년 전 1

시간 초과 질문드립니다.

priority queue를 사용할 때, pair와 struct가 어떤 시간 차이가 있는지 궁금합니다.

pair<int, pair<int, int>>를 사용하고 cmp 대신 아래 코드 처럼 priority queue를 작성하는 경우 시간초과가 발생하지 않습니다.

priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq

반면, 아래 코드 처럼 struct Node를 사용하고 cmp 구조체를 사용하면 시간초과가 발생합니다.

struct Node{
    int w, r, c;
};

struct cmp{
    bool operator()(Node a, Node b){
        if(a.r == b.r && a.c == b.c){
            if(a.w > b.w) return true;
        }
    }
};

priority_queue<Node, vector<Node>, cmp> pq;

어떤 차이가 있는 것인지 궁금합니다.

소스 코드는 시간 초과가 난 소스 입니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
int N, cnt=0;
int board[125][125];
int dist[125][125];

struct Node{
    int w, r, c;
};

struct cmp{
    bool operator()(Node a, Node b){
        if(a.r == b.r && a.c == b.c){
            if(a.w > b.w) return true;
        }
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    while(true)
    {
        cnt++;
        cin >> N;
        if(N == 0) break;
        for(int i=0;i<N;i++)
        {
            fill(dist[i], dist[i]+N, 1e9);
            for(int j=0;j<N;j++)
                cin >> board[i][j];
        }

        priority_queue<Node, vector<Node>, cmp> pq;
        pq.push({board[0][0],0,0});
        dist[0][0] = board[0][0];
        while(!pq.empty())
        {
            auto cur = pq.top(); pq.pop();
            for(int dir=0;dir<4;dir++)
            {
                int nr = cur.r + dr[dir];
                int nc = cur.c + dc[dir];
                if(nr<0 or nc<0 or nr>=N or nc>=N) continue;
                
                int cost = dist[cur.r][cur.c] + board[nr][nc];
                if(dist[nr][nc] <= cost) continue;
                dist[nr][nc] = cost;
                pq.push({cost,nr,nc});
            }
        }
        cout << "Problem " << cnt << ": " << dist[N-1][N-1]<< '\n';
    }
}

yuris 1년 전 0

cmp 구조체 에서 r과 c가 같지 않으면 아무런 반환을 하지 않습니다.

cejung 1년 전 0

@yuris

답변감사드립니다.

해당 코드에서 첫번째 if 문 지워도 시간초과는 똑같이 나네요 ㅠㅠ

struct cmp{
    bool operator()(Node a, Node b){
        if(a.r == b.r && a.c == b.c){
            if(a.w > b.w) return true;
        }
    }
};

yuris 1년 전 0

if문을 지워도 (a.w > b.w)조건이 맞지 않으면 값을 반환하지 않습니다. 조건에 맞지 않는 경우에 false값을 반환해줘야 제대로 된 비교 함수로 사용될 수 있습니다.

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

문제

문제

출처

ICPC

struct, pair 차이에 따른 "시간 초과" 질문

cejung 1년 전 1

yuris 1년 전 0

cejung 1년 전 0

yuris 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말