글 읽기 - 2580 스도쿠 시간초과... 답을 모르겠습니다.

sd3503 2년 전 0

해당 문제에서 모두 0만 집어넣어서 연산을 해도 입력시간을 뺀 연산시간+출력시간이 24ms안쪽으로 나오는걸 확인 했습니다. 나머지 경우는 뭐 볼 필요도 없겠죠 그런데도 시간초과가 납니다. 고수님들 답변 해주시면 감사하겠습니다.

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

namespace CountingSort
{
    class Program
    {
        static int[] intArrayGloval = new int[81];
        static void Main(string[] args)
        {
            StringBuilder stringv = new StringBuilder();
            for (var i = 0; i < 9; i++)
            {
                var textArray = Console.ReadLine().Split(" ");
                for (var j = 0; j < 9; j++)
                {
                    intArrayGloval[i*9 + j] = Convert.ToInt32(textArray[j]); 
                }
            }
            dfs(intArrayGloval);
            for (var i = 0; i < 9; i++)
            {
                for (var j = 0; j < 9; j++)
                {
                    stringv.Append(intArrayGloval[i * 9 + j] + " ");
                }
                stringv.Append("\n");
            }
            Console.WriteLine(stringv);
        }
        public static void dfs(int[] intArray)
        {
            var intArrayLocal = (int[])intArray.Clone();
            if (!intArray.Contains(0))
            {
                if (intArrayGloval.Contains(0))
                {
                    intArrayGloval = intArrayLocal;
                }    
                return;
            }
            for (var i = 0; i < 81; i++)
            {
                if (intArray[i] > 0)
                {
                    continue;
                }
                var ableArray = getAbleArray(i, intArrayLocal);
                if (ableArray.Count() <= 0)
                {
                    break;
                }
                foreach (var ableInt in ableArray)
                {
                    if (!intArrayGloval.Contains(0))
                    {
                        break;
                    }
                    intArrayLocal[i] = ableInt;
                    dfs(intArrayLocal);
                }

            }

        }
        public static IEnumerable<int> getAbleArray(int curruntIDX,int[] intArrayLocal)
        {
            var returnArr = new int[9];
            for (var i = 0; i < 9; i++)
            {
                returnArr[i] = i + 1;
            }
            var rowIndex = 0;
            for (var i = 0; i < 9; i++)
            {
                //초기값 + 변동값
                rowIndex = curruntIDX / 9 * 9 + i;
                if (intArrayLocal[rowIndex] != 0)
                {
                    returnArr[intArrayLocal[rowIndex] - 1] = 0;
                }
                rowIndex = curruntIDX % 9 + i * 9;
                if (intArrayLocal[rowIndex] != 0)
                {
                    returnArr[intArrayLocal[rowIndex] - 1] = 0;
                }
                rowIndex = curruntIDX / 27* 27 + curruntIDX % 9 / 3 * 3 + i % 3 + (i/3)*9;
                if (intArrayLocal[rowIndex] != 0)
                {
                    returnArr[intArrayLocal[rowIndex] - 1] = 0;
                }
            }
            return returnArr.Where(x => x != 0);
        }
    }
}

analog2003 1년 전 0

모두 0넣으면 원래 엄청 빨라요.. 저도 방금해보니 8ms 나오네요

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

문제

문제

출처

ICPC

2580 스도쿠 시간초과... 답을 모르겠습니다.

sd3503 2년 전 0

analog2003 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말