글 읽기 - 우선순위 큐의 일관성이 깨지면 안되네요. (자문자답)

bacon8282 3년 전 1

아무리 생각해도 맞는것 같았고, 질문 게시판의 반례도 다 통과한 것 같은데도 안되서 곰곰히 생각을 해봤는데,

우선순위 큐에 있는 원소가 같고 있는 '우선순위에 영향을 주는 요인'(여기서는 Distance 였겠죠.)을 외부에서 건드려서 우선순위가 뒤바뀌면 큰 문제가 된다는 걸 깨달았습니다.

정점의 거리를 갱신할 때, 우선순위 큐의 일관성에는 영향이 없어야 한다는 것이었네요. 삽질 끝에 우선순위 큐의 작동 원리에 대해 좀 더 이해해갑니다.

아래 코드는 오답이에용.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon
{
    class VertexHeap
    {
        readonly List<Vertex> heapItems = new List<Vertex>();
        public int Count { get; private set; }

        public void Push(Vertex item)
        {
            heapItems.Add(null);

            int pos = Count++;
            int parent = (pos - 1) / 2;
            while (pos > 0 && Compare(item, heapItems[parent]) > 0)
            {
                heapItems[pos] = heapItems[parent];
                pos = parent;
                parent = (pos - 1) / 2;
            }
            heapItems[pos] = item;
        }

        public Vertex Pop()
        {
            Vertex output = heapItems[0];
            heapItems[0] = heapItems[--Count];

            int parent = 0;
            int child = 1;
            while (child < Count)
            {
                if (child + 1 < Count && Compare(heapItems[child + 1], heapItems[child]) > 0)
                    child++;

                if (Compare(heapItems[parent], heapItems[child]) > 0)
                    break;

                Swap(parent, child);
                parent = child;
                child = 2 * child + 1;
            }

            return output;
        }

        private int Compare(Vertex a, Vertex b)
        {
            return b.Distance - a.Distance;
        }

        private void Swap(int a, int b)
        {
            Vertex hold = heapItems[a];
            heapItems[a] = heapItems[b];
            heapItems[b] = hold;
        }
    }

    class Vertex
    {
        readonly List<Edge> edges = new List<Edge>();

        public bool IsTraversed { get; private set; } = false;
        public int Distance { get; private set; } = int.MaxValue;

        public void LinkVertex(Vertex dest, int weight)
        {
            edges.Add(new Edge(dest, weight));
        }

        public void UpdateDistance()
        {
            VertexHeap heap = new VertexHeap();
            heap.Push(this);
            Distance = 0;

            while (heap.Count > 0)
            {
                Vertex curVertex = heap.Pop();
                if (curVertex.IsTraversed)
                    continue;

                foreach (Edge e in curVertex.edges)
                {
                    if (e.dest.Distance > curVertex.Distance + e.weight)
                    {
                        e.dest.Distance = curVertex.Distance + e.weight;
                        heap.Push(e.dest);
                    }
                }

                curVertex.IsTraversed = true;
            }
        }

        class Edge
        {
            public readonly Vertex dest;
            public readonly int weight;

            public Edge(Vertex dest, int weight)
            {
                this.dest = dest;
                this.weight = weight;
            }
        }
    }

    class Program
    {
        static Vertex[] vertices;
        static Vertex startVertex;

        static void LinkVertex(int a, int b, int w)
        {
            vertices[a].LinkVertex(vertices[b], w);
        }

        static void ReadInputs()
        {
            int[] buffer = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            vertices = new Vertex[buffer[0] + 1];
            for (int i = 1; i < vertices.Length; i++)
                vertices[i] = new Vertex();
            int edgeNum = buffer[1];

            startVertex = vertices[int.Parse(Console.ReadLine())];

            for (int i = 0; i < edgeNum; i++)
            {
                buffer = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
                LinkVertex(buffer[0], buffer[1], buffer[2]);
            }
        }

        static void WriteOuputs()
        {
            startVertex.UpdateDistance();
            StringBuilder output = new StringBuilder();
            for(int i = 1; i < vertices.Length; i++)
                output.AppendLine(vertices[i].IsTraversed ? vertices[i].Distance.ToString() : "INF");
            Console.Write(output);
        }

        static void Main(string[] args)
        {
            ReadInputs();
            WriteOuputs();
        }
    }
}

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

문제

문제

출처

ICPC

우선순위 큐의 일관성이 깨지면 안되네요. (자문자답)

bacon8282 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말