글 읽기 - C++] 프림 알고리즘으로 풀었는데 틀렸습니다가 바로 나옵니다.

dlqudgus2587 3년 전 0

프림 알고리즘으로 풀었는데 %올라가는 것도 없이 바로 틀렸습니다가 나옵니다.

최소 비용 찾는 것은 우선순위 큐를 이용했습니다.(while문 내에서 먼저 현재 정점을 방문하고, 연결된 간선 중에서 아직 방문하지 않은 노드랑 연결되어 있는 간선은 우선 순위 큐에 넣어주는 식으로 구현했습니다.)

게시판에 있는 반례까지 다 넣어봤는데 바로 틀렸습니다가 나오네요ㅠ 어떤 점이 잘못 되었는지 지적해주시면 감사하겠습니다!

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

struct comp {
  bool operator()(pair<int, int>a, pair<int, int> b)
  {
    return a.second > b.second;
  }
};

int main()
{
  int V, E,f,t,w, e = 0, cur;
  pair<int, int> min;
  int cost = 0;
  scanf("%d %d", &V, &E);
  vector<pair<int, int>> adj[V+1]; //first=des, second = w
  priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;

  int visit[V+1] = {0, };
  for(int i = 0; i<E; i++)
  {
    scanf("%d %d %d", &f, &t, &w);
    adj[f].push_back(make_pair(t, w));
    adj[t].push_back(make_pair(f, w));
  }

  cur = f;
  while(e+1 < V)
  {
    visit[cur] = 1;
    for(auto next: adj[cur])
    {
      if(!visit[next.first])
      {
        pq.push(next);
      }
    }
    min = pq.top();
    pq.pop();
    cost += min.second;
    e++; 
    cur = min.first;
  }
  printf("%d", cost);
}

moon960323 3년 전 1

visit 배열을 pq에 넣을 때만 확인하면 되는건지? 관찰해보시면 틀린 부분을 찾을 수 있을겁니다.

dlqudgus2587 3년 전 0

@moon960323 님 답변 감사드립니다!

말씀해주신대로 visit배열을 추가적으로 pq에서 pop할 때도 체크해줘야 하는 것을 확인하고 수정했더니 통과됐습니다. 도움주셔서 정말 감사드립니다.

그리고 추가적으로 궁금한 점이 생겼는데, 실례가 안된다면 혹시 제 코드만 보고 바로 반례가 떠오르신건지 궁금합니다!

감사합니다.

moon960323 3년 전 1

네 저도 예전에 코딩을 했을 때 visit을 확인해주는 부분을 놓친적이 많아가지고

반례가 바로 보였던 것 같습니다.

dlqudgus2587 3년 전 0

@moon960323 아무리 그래도 대단하시네요ㅠㅠ 공부를 많이 해야할 것 같네요 저도ㅋㅋ 시간내서 답변해주셔서 감사드립니다!!

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

문제

문제

출처

ICPC

C++] 프림 알고리즘으로 풀었는데 틀렸습니다가 바로 나옵니다.

dlqudgus2587 3년 전 0

moon960323 3년 전 1

dlqudgus2587 3년 전 0

moon960323 3년 전 1

dlqudgus2587 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말