글 읽기 - 시간초과가 어디서 나는지 모르겠어요

paraworld 4년 전 0

질문들도 찾아보고 구글링도 해봤는데 어디서 시간 초과가 나는지 모르겠습니다..

제발 좀 알려주시면 감사하겠습니다. 예전에 스토쿠 문제 푸는데 3일 걸렸는데 이 문제도 그렇게 될 판입니다;;

C#이라 우선순위 큐는 리스트로 만들었습니다

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

namespace Testpad
{
    public class BaekJoon1753
    {
        // 간선들의 목록, key = 도착점, value = 가중치, [] = 시작점
        static SortedDictionary<int, int>[] lines;

        // 정점까지의 최단거리
        static int[] shortestPath;

        // 다익스트라용 우선순위 '큐', 값은 시작점 번호
        static List<int> priorList = new List<int>();

        static void Main()
        {
            StringBuilder sb = new StringBuilder();

            string[] inputs = Console.ReadLine().Split(" ");
            int v = int.Parse(inputs[0]); // 정점의 개수 v
            int e = int.Parse(inputs[1]); // 간선의 개수 e
            int k = int.Parse(Console.ReadLine()); // 시작점의 번호 k

            lines = new SortedDictionary<int, int>[v];

            // 정점들 연결 상태를 초기화
            for (int i = 0; i < v; i++)
            {
                lines[i] = new SortedDictionary<int, int>();
            }

            // 간선들의 정보
            for (int i = 0; i < e; i++)
            {
                string[] inputs2 = Console.ReadLine().Split(" ");

                // a에서 b로 가는 가중치 c짜리 간선
                int a = int.Parse(inputs2[0]);
                int b = int.Parse(inputs2[1]);
                int c = int.Parse(inputs2[2]);

                try
                {
                    lines[a - 1].Add(b - 1, c);
                }
                // 중복되는 느린 경로는 제거
                catch (ArgumentException)
                {
                    if (lines[a - 1][b - 1] > c)
                    {
                        lines[a - 1][b - 1] = c;
                    }
                }
            }

            // 최단거리를 찾음
            Dijkstra(v, k - 1);

            for (int i = 0; i < v; i++)
            {
                if (shortestPath[i] != int.MaxValue)
                {
                    sb.Append(shortestPath[i]);
                    sb.AppendLine();
                }
                // 경로가 존재하지 않으면 INF 출력
                else
                {
                    sb.AppendLine("INF");
                }
            }

            Console.Write(sb.ToString());
        }

        // v = 정점의 개수, k = 시작점의 번호
        static void Dijkstra(int v, int k)
        {
            priorList.Add(k); // 시작점을 리스트에 넣음

            shortestPath = new int[v]; // 해당 정점까지의 최단거리

            // 최단거리는 일단 '무한대'로 놓음
            for (int i = 0; i < v; i++)
            {
                shortestPath[i] = int.MaxValue;
            }

            shortestPath[k] = 0; // 시작점 자신과의 거리는 0

            while (priorList.Count > 0)
            {
                // 새로 찾은 점들 리스트, key = 점 번호, value = 시작점과의 거리
                // 시작점은 하나이니 key값이 중복될 일은 없음
                Dictionary<int, int> dots = new Dictionary<int, int>();

                int target = priorList[0]; // 정점 target을 중심으로 전부 둘러봄

                foreach (var item in lines[target])
                {
                    // 아직 방문하지 않은 정점인 경우
                    if (shortestPath[item.Key] == int.MaxValue)
                    {
                        shortestPath[item.Key] = shortestPath[target] + item.Value;

                        // 현재 가중치나 큐에 넣은 순서로 우선순위 큐를 정하면 망한다.
                        dots.Add(item.Key, shortestPath[item.Key]);
                    }
                    // 해당 정점까지의 더 짧은 거리가 나온 경우
                    else if (shortestPath[item.Key] > shortestPath[target] + item.Value)
                    {
                        shortestPath[item.Key] = shortestPath[target] + item.Value;
                        dots[item.Key] = shortestPath[item.Key];
                    }
                }

                BinaryRemove();

                // 다익스트라 알고리즘은 루프마다 항상 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 정점을 뽑아야 합니다.
                BinaryAdd(dots);
            }
        }

        // 가장 짧은 거리를 찾는 것은 그냥 하면 O(n)이니, 우선순위 큐를 사용해 O(logN)으로 줄임
        // 우선순위 큐에 자료를 추가하는 연산
        // dots = 이번에 추가할 점들 번호와 가중치
        static void BinaryAdd(Dictionary<int, int> dots)
        {
            foreach (var item in dots)
            {
                priorList.Add(item.Key); // 리스트에 넣고, 부모 노드와 비교함

                int min = 0;
                int max = priorList.Count - 1;

                while (min < max)
                {
                    int pivot = min + (max - min - 1) / 2; // 기준점
                    int parent = priorList[pivot]; // 부모 노드

                    if (item.Value < parent)
                    {
                        Swap(max, pivot);
                        max = pivot;
                    }
                    else
                    {
                        break;
                    }
                }
            }            
        }

        // 우선순위 '큐'에서 자료를 제거하는 연산
        static void BinaryRemove()
        {
            int min = 0;
            int max = priorList.Count - 1;

            // 제거할 자료를 맨 뒤의 자료와 바꾸고 제거함
            Swap(0, max);
            priorList.RemoveAt(max);
            max--;

            // 임시로 맨 앞에 온 자료를 재배열함
            while (min < max)
            {
                int target = priorList[min]; // 임시로 맨 앞에 온 자료

                int pivot = min * 2 + 1; // 기준점

                // 자식 노드가 2개인 경우, 더 작은 쪽과 비교함
                if (pivot < max)
                {
                    if (priorList[pivot] > priorList[pivot + 1])
                    {
                        pivot++;
                    }
                }

                if (pivot > max || target > priorList[pivot])
                {
                    break;
                }
                else
                {
                    Swap(min, pivot);
                    min = pivot;
                }
            }
        }

        // 두 수 x, y를 바꾸는 연산
        static void Swap(int x, int y)
        { 
            int temp = priorList[y];
            priorList[y] = priorList[x];
            priorList[x] = temp;
        }
    }
}

paraworld 4년 전 0

코드를 갈아엎어서 해결했습니다만... 이번엔 계속 '틀렸습니다' 가 뜨네요;;

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

문제

문제

출처

ICPC

시간초과가 어디서 나는지 모르겠어요

paraworld 4년 전 0

paraworld 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말