글 읽기 - 시간초과 질문합니다.

blue_sau 4년 전 0

우선 이분매칭을 사용하였습니다.

그룹 a,b로 노드들을 구성하고, 이 노드들을 매칭시키는 방법을 사용했습니다.

코드 작동과정을 쉽게 보실 수 있게 주석을 달아놓았습니다.

문제는 결과값은 잘 나오고, n = 50인 시간복잡도가 최대인 상황에서 탐색을 진행해도, 반복 횟수도 그다지 크지 않고, 정답도 맞게 나왔습니다.

또한 시간 초과의 원인을 입출력 지연에서 찾아봤지만, 출력하는 양이 크기 않아서 이도 크게 상관이 없다고 판단됩니다.

부하를 최대로 주기 위해서 사용했던 테스트 케이스들입니다.

50
1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 970 969 968 967 966 965 964 963 962 961 960 959 958 957 956 955 954 953 952 951

50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

이런 문턱 테스트 케이스도, 무한 제귀나, 큰 시간복잡도 없이 완료하는 것을 확인했습니다.

일반적인 테스트 케이스들에 대해서 답은 다 맞는 상태인데, 시간 초과가 발목을 잡네요 ㅠㅠ

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

namespace BOJ17
{
    // 소수들의 모음
    class Primes
    {
        private List<int> primes = new List<int>();

        public Primes(int count)
        {
            int sqrt = (int)MathF.Sqrt(count);
            for (int i = 2; i < count; i++)
            {
                primes.Add(i);
            }
            for (int i = 2; i < sqrt; i++)
            {
                int max = count / i;
                for (int j = 2; j <= max; j++)
                {
                    primes.Remove(i * j);
                }
            }
        }

        // 이 수가 소수인지 반환
        public bool isPrime(int i)
        {
            return primes.Contains(i);
        }
    }

    class Node
    {
        public int value;
        public List<int> attatchedNodes; // 연결된 노드들의 배열상에서의 인덱스
        private bool neverMove = false;

        public Node(int value)
        {
            this.value = value;
            this.attatchedNodes = new List<int>();
        }

        // 이 노드를 고정한다
        public void pivot()
        {
            this.neverMove = true;
        }

        // 다른 노드와 매칭 가능한지 반환하고, 해당 노드와 매칭한다.
        public bool CanChange(List<Node> visited, Stack<Node> node2Skip)
        {
            if (neverMove)// 고정 노드는 매칭 변경 불가능
            {
                return false;
            }
            // 자신으로 탐색이 돌아온다면, 탐색이 실패한 것임
            if (node2Skip.Contains(this))
            {
                return false;
            }
            // 다른 매칭 가능한 노드를 탐색
            for (int i = 0; i < attatchedNodes.Count; i++)
            {
                if (visited[attatchedNodes[i]] == null)
                {
                    visited[attatchedNodes[i]] = this;
                    return true;
                }
                else // 이미 사용중인 노드라면, 양보 가능한지 확인한다.
                {
                    node2Skip.Push(this);
                    if (visited[attatchedNodes[i]].CanChange(visited, node2Skip))
                    {
                        visited[attatchedNodes[i]] = this;
                        return true;
                    }
                    node2Skip.Pop();
                }
            }
            return false;
        }
    }


    class Traveler
    {
        private List<int> a, b;
        private List<Node> nodes;
        private List<Node> visited;

        public Traveler(List<int> a, List<int> b)
        {
            this.a = a;
            this.b = b;
            nodes = new List<Node>();
        }

        // a그룹에 대하여, b그룹의 노드를 연결하여, 그래프를 구성함
        private void BuildNode()
        {
            Primes primes = new Primes(2000);
            for (int i = 0; i < a.Count; i++)
            {
                Node node = new Node(a[i]);
                for (int j = 0; j < b.Count; j++)
                {
                    if (primes.isPrime(a[i] + b[j]))// 소수면, 연결함
                    {
                        node.attatchedNodes.Add(j);
                    }
                }
                nodes.Add(node);
            }
        }

        // a그룹의 노드들에 대하여, b그룹의 노드들을 매칭한다.
        private bool Matching()
        {
            // 0번 노드는 이미 매칭되어있으므로 생략하고
            for (int i = 1; i < nodes.Count; i++)
            {
                bool notOk = true;// 매칭 실패여부
                // i번째 노드에 대하여, 매칭 가능한 노드를 탐색
                for (int j = 0; j < nodes[i].attatchedNodes.Count; j++)
                {
                    if (visited[nodes[i].attatchedNodes[j]] == null) // 매칭 가능
                    {
                        visited[nodes[i].attatchedNodes[j]] = nodes[i];
                        notOk = false;
                        break;
                    }
                    else
                    {
                        if (visited[nodes[i].attatchedNodes[j]].CanChange(visited, new Stack<Node>())) // 불가능 하다면 이미 매칭된 노드에게 변경 가능한지 확인함
                        {
                            visited[nodes[i].attatchedNodes[j]] = nodes[i];
                            notOk = false;
                            break;
                        }
                    }
                }
                if (notOk)
                {
                    return false;
                }
            }
            return true;
        }

        // 결과를 반환한다. 결과는, 매칭 가능한 숫자들의 리스트
        public List<int> GetResult()
        {
            List<int> result = new List<int>();
            BuildNode();// 그래프를 구성함
            nodes[0].pivot();// 0번 노드는 한번 매칭한 노드를 변경할 수 없음
            for (int i = 0; i < nodes[0].attatchedNodes.Count; i++)// 0번 노드와 연결 가능한 노드들에 대하여 매칭
            {
                visited = new List<Node>();// 방문한 노드 목록 초기화
                for (int j = 0; j < 25; j++)
                {
                    visited.Add(null);
                }
                visited[nodes[0].attatchedNodes[i]] = nodes[0];//0번 노드의 i번 노드를 0번 노드와 매칭시킴
                if (Matching())// 매칭에 성공했다면
                {
                    result.Add(b[nodes[0].attatchedNodes[i]]);// 추가함
                }
            }
            result.Sort();//정렬하고
            return result;
        }
    }



    class Program
    {
        static void Main(string[] args)
        {
            // 인풋 처리부
            int count;
            string input;
            string[] parses;
            List<int> nums = new List<int>();
            List<int> odd = new List<int>();
            List<int> even = new List<int>();
            Traveler traveler;
            input = Console.ReadLine();
            count = int.Parse(input);
            input = Console.ReadLine();
            parses = input.Split(" ");

            // 홀수개라면 무조건 거짓
            if (count % 2 == 1)
            {
                Console.WriteLine("-1");
                return;
            }

            // 문자열을 숫자로 변환과정
            // 짝수, 홀수 그룹으로 분류
            for (int i = 0; i < count; i++)
            {
                nums.Add(int.Parse(parses[i]));
                if (nums[i] % 2 == 0)
                {
                    even.Add(nums[i]);
                }
                else
                {
                    odd.Add(nums[i]);
                }
            }

            // 두 그룹의 크기가 다르다면, 분류 불가
            if (even.Count != odd.Count)
            {
                Console.WriteLine("-1");
                return;
            }

            // 홀, 짝에 따라서 첫 수를 설정
            if (nums[0] % 2 == 0)
            {
                traveler = new Traveler(even, odd);
            }
            else
            {
                traveler = new Traveler(odd, even);
            }
            List<int> result = traveler.GetResult();

            // 하나도 없다면 실패한 것임.
            if (result.Count == 0)
            {
                Console.WriteLine("-1");
                return;
            }

            for (int i = 0; i < result.Count; i++)
            {
                Console.Write(result[i] + " ");
            }
            Console.WriteLine();
        }
    }
}

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

문제

문제

출처

ICPC

시간초과 질문합니다.

blue_sau 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말