글 읽기 - 13549 우선순위 cmp기준 관련 질문

jinny9650 1년 전 0

std에 있는 pair을 이용하여, greater순으로 우선순위 큐에서 뽑았을땐 맞는 답이 나오지만,

pair 구조체와 cmp 기준을 만들어서 풀이했을 땐 오답이 나옵니다.

cmp기준을 저렇게 작성하면 greater과 동일하게 time이 작은것 부터 추출하는게 맞지 않나요? 왜 틀린걸까요...?

//오답코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

bool visited[100001];
int N, K;

struct pair{
    int time;
    int cur_point;
}; // 탐색순위, 시간이 적게걸린거 먼저.

struct cmp{
    bool operator()(pair A,pair B) {
        return A.time>B.time;
    }
};
std::priority_queue<pair,std::vector<pair>,cmp> pQ;

void bfs() {

    pQ.push({0,N});
    visited[N]=true;

    while(!pQ.empty()) {
        int point=pQ.top().cur_point;
        int time=pQ.top().time;
        pQ.pop();

        if(point==K) {
            std::cout << time;
            return;
        }

        if(point*2<=100000&&!visited[point*2]) {
            pQ.push({time,point*2});
            visited[point*2]=true;
        }
        if(point-1>=0&&!visited[point-1]) {
            pQ.push({time+1,point-1});
            visited[point-1]=true;
        }
        if(point+1<=100000&&!visited[point+1]) {
            pQ.push({time+1,point+1});
            visited[point+1]=true;
        }

    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    std::cin >> N >> K;

    bfs();

    return 0;
}

//정답코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

bool visited[100001];
int N, K;

std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>> pQ;

void bfs() {

    pQ.push({0,N});
    visited[N]=true;

    while(!pQ.empty()) {
        int point=pQ.top().second;
        int time=pQ.top().first;
        pQ.pop();

        if(point==K) {
            std::cout << time;
            return;
        }

        if(point*2<=100000&&!visited[point*2]) {
            pQ.push({time,point*2});
            visited[point*2]=true;
        }
        if(point-1>=0&&!visited[point-1]) {
            pQ.push({time+1,point-1});
            visited[point-1]=true;
        }
        if(point+1<=100000&&!visited[point+1]) {
            pQ.push({time+1,point+1});
            visited[point+1]=true;
        }

    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    std::cin >> N >> K;

    bfs();

    return 0;
}

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

문제

문제

출처

ICPC

13549 우선순위 cmp기준 관련 질문

jinny9650 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말