iwtkmn   1년 전

struct와 직접 만든 비교 함수를 사용하여 제출했을 때는 시간 초과가 발생하지만, pair와 greater<> 함수를 사용하였을 때는 무난히 통과가 됩니다 ㅠㅠ

- 원래 코드(struct)

struct point {
    int dis, row, col;
};

struct compare {
    bool operator()(const point &p1, const point &p2) {
        if (p1.dis != p2.dis) return p1.dis > p2.dis;
        else if (p1.row != p2.row) return p1.row < p2.row;
        else return p1.col < p2.col;
    }
};

priority_queue<point, vector<point>, compare> pq;

- 수정 코드(pair)

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

통과는 잘 됐지만 이유를 도통 모르겠습니다.. 이유를 아시는 분은 저 좀 살려주십쇼.. ㅠㅠㅠㅠㅠ

djm03178   1년 전

틀린 코드 전체 그대로를 올려주시면 문제점을 찾는 데에 큰 도움이 됩니다.

https://djm03178.tistory.com/6

올려주신 코드에서 point를 사용하도록 제가 직접 수정해보았을 땐 잘 통과됩니다.

http://boj.kr/a099520d449c4540...

thinker99   1년 전

https://gcc.gnu.org/onlinedocs...
std::pair도 결국 libstdc++에서 struct로 구현되어 있습니다만..

iwtkmn   1년 전

죄송합니다 틀린코드를 올린다는게..

이게 제가 제출한 틀린 시간 초과 코드입니다

djm03178   1년 전

priority_queue은 큰 원소의 우선순위를 높게 쳐주기 때문에 비교 연산자에서 p1.dis > p2.dis로 비교했다면 거리가 가까운 것의 dis값이 작아야 합니다. 그렇기 때문에 지금 상태의 비교 연산자를 사용하려면 dis를 pq에 넣고 뺄 때 음수로 바꿀 필요가 없습니다. 원래 코드에서 하셨던 것처럼 양수 거리를 그대로 넣고 빼면 됩니다.

iwtkmn   1년 전

아.. 지금 보니 잘 만들어놓고 원래 pq쓰던대로 코드를 써놨네요.. 감사하고 죄송합니다..

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