글 읽기 - 배열이 아닌 우선순위 큐를 사용할 때는 실패하는 이유는 무엇인지 궁급합니다.

kimby469 3년 전 1

제목 그대로 리스트로 하고 정렬을 할때는 맞는다고 답이나오는데.. 우선순위큐는 왜 안되는지 이유를 전혀 모르겠습니다. 혹시 이 부분에 대해서 아신다면 댓글 부탁드려요 ㅠㅠ

코드 설명 : 시작 정적,도착 정점,간선의비용 을 담은 Node 객체를 타입으로 하여 우선순위 큐 또는 리스트에 간선을 기준으로 하여 정렬을 하였으며 그 후 서로소 집합 알고리즘을 이용하여 사이클의 여부를 판단하고 이미 리스트나 우선순위 큐에는 간선이 제일 작은 것이 먼저인 오름차순으로 정렬을 해놓은 상태로 크루스칼 알고리즘의 원리를 녹여내어 구현 하였습니다.

package oneDay_twoSol.graphTheory.Grouping;

import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class MST {
    static int parent[];
    static PriorityQueue<Node> pq=new PriorityQueue<>();
    static ArrayList<Node> list=new ArrayList<>();
    static class Node implements Comparable<Node>
    {
        private int v1,v2,dist;

        public Node(int v1, int v2, int dist) {
            this.v1 = v1;
            this.v2 = v2;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            if(this.dist-o.dist==0)
                return this.v1-o.v1;
            return this.dist-o.dist;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        int v=sc.nextInt();
        parent=new int[v+1];
        for (int i = 1; i < v+1; i++) {
            parent[i]=i;
        }
        int e=sc.nextInt();
        for (int i = 0; i < e; i++) {
            pq.offer(new Node(sc.nextInt(),sc.nextInt(),sc.nextInt()));
//            list.add(new Node(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        }
        Collections.sort(list);
        int ans=0;
        for (Node node : pq) {
            if(find(node.v1)!=find(node.v2))
            {
                union(node.v1,node.v2);
                ans+=node.dist;
            }
        }
        System.out.println(ans);

    }
    static void union(int a,int b)
    {
        a=find(a);
        b=find(b);
        if(a<b)
            parent[b]=a;
        else
            parent[a]=b;
    }
    static int find(int a)
    {
        if(parent[a]==a)
            return a;
        return parent[a]=find(parent[a]);
    }

}

mrseos 3년 전 1

우선순위 큐도 가능합니다.

단 정렬 순서를 보장받기 위해서는 poll()을 해줘야합니다.

아래 코드는 채점번호 : 26415290에 제출된 코드입니다.

import java.util.*;
class Node implements Comparable<Node> {
    int v1,v2,dist;
    public Node(int v1, int v2, int dist) {
        this.v1 = v1;
        this.v2 = v2;
        this.dist = dist;
    }
    @Override
    public int compareTo(Node o) {
        if(this.dist-o.dist==0)
            return this.v1-o.v1;
        return this.dist-o.dist;
    }
}
public class Main {
	static int parent[];
    static PriorityQueue<Node> pq=new PriorityQueue<>();
    static ArrayList<Node> list=new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        int v=sc.nextInt();
        parent=new int[v+1];
        for (int i = 1; i < v+1; i++) {
            parent[i]=i;
        }
        int e=sc.nextInt();
        for (int i = 0; i < e; i++) {
            pq.offer(new Node(sc.nextInt(),sc.nextInt(),sc.nextInt()));
//            list.add(new Node(sc.nextInt(),sc.nextInt(),sc.nextInt()));
        }
        Collections.sort(list);
        int ans=0;
        while(!pq.isEmpty()) {
        	Node node = pq.poll();
            if(find(node.v1)!=find(node.v2))
            {
                union(node.v1,node.v2);
                ans+=node.dist;
            }
        }
        System.out.println(ans);

    }
    static void union(int a,int b)
    {
        a=find(a);
        b=find(b);
        if(a<b)
            parent[b]=a;
        else
            parent[a]=b;
    }
    static int find(int a)
    {
        if(parent[a]==a)
            return a;
        return parent[a]=find(parent[a]);
    }
}

kimby469 3년 전 0

감사합니다. 덕분에 우선순위 큐에 대한 순회는 정렬된 순서가 아니라는 것을 알게 되었습니다. 컬렉션 라이브러리에 대해 더 공부해야 겠습니다.

- 정렬된 순서대로 순회되지 않음.

- 들어간 순서도 아님. [0] 에 poll() 할 요소만 와있는 상태.

mrseos 댓글 감사합니다!

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

문제

문제

출처

ICPC

배열이 아닌 우선순위 큐를 사용할 때는 실패하는 이유는 무엇인지 궁급합니다.

kimby469 3년 전 1

mrseos 3년 전 1

kimby469 3년 전 0

mrseos 댓글 감사합니다!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말