글 읽기 - 시간초과가 나는데 시간을 어떻게 줄여야 할 지 모르겠습니다(C#)

wjddn7118 2년 전 0

대략적인 코드는 다 짜놨는데 답이 나오는 것 까지는 문제가 없습니다. 하지만 계속 시간초과가 나옵니다.

어떻게든 줄여보려고 예시의 배열이 저장된 arr을 1차원 배열 2개로 쪼개서 Array.IndexOf도 써보고 해봤는데

시간복잡도가 개선이 되지 않아서 이렇게 글을 쓰게 되었습니다. 도와주셨으면 합니다.

(추가로 제가 아직 시간복잡도에 대해 잘 몰라서 그러는데 제 코드의 시간복잡도 까지 가르쳐주시면 감사하겠습니다.)

static int n;
    static int m;
    static int[,] arr;
    static bool[] visit;
    static bool done = false;
    static void Main()
    {
        int[] tmp1 = Array.ConvertAll(ReadLine().Split(), Int32.Parse);
        n = tmp1[0];    // 사람의 수
        m = tmp1[1];    // 친구 관계의 수

        if(m < 4)
        {
            WriteLine("0");
            return;
        }

        arr = new int[m, 2];
        visit = new bool[n];
        for (int i = 0; i < m; i++)
        {
            tmp1 = Array.ConvertAll(ReadLine().Split(), Int32.Parse);
            arr[i, 0] = tmp1[0];
            arr[i, 1] = tmp1[1];
        }

		
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                visit[arr[i, j]] = true;
                Relation(i, j, 0);
                visit[arr[i, j]] = false;
            }
        }

		
        if (done)
            WriteLine("1");
        else
            WriteLine("0");
    }

	
    static void Relation(int a, int b, int count)
    {
        if (done)
            return;

        if (b == 0 && !visit[arr[a, 1]])
        {
            count++;
            if (count == 4)
            {
                done = true;
                return;
            }

            visit[arr[a, 1]] = true;
			for(int i = 0; i < a; i++)
			{
				if(arr[i, 0] == arr[a, 1])
                {
                    Relation(i, 0, count);
                }
                else if (arr[i, 1] == arr[a, 1])
                {
                    Relation(i, 1, count);
                }
			}
            for (int i = a + 1; i < m; i++)
            {
				if(arr[i, 0] == arr[a, 1])
                {
                    Relation(i, 0, count);
                }
                else if (arr[i, 1] == arr[a, 1])
                {
                    Relation(i, 1, count);
                }
            }
            visit[arr[a, 1]] = false;
        }
        else if (b == 1 && !visit[arr[a, 0]])
        {
            count++;
            if (count == 4)
            {
                done = true;
                return;
            }

            visit[arr[a, 0]] = true;
			
			for(int i = 0; i < a; i++)
			{
				if(arr[i, 0] == arr[a, 0])
                {
                    Relation(i, 0, count);
                }
                else if (arr[i, 1] == arr[a, 0])
                {
                    Relation(i, 1, count);
                }
			}
            for (int i = a + 1; i < m; i++)
            {
				if(arr[i, 0] == arr[a, 0])
                {
                    Relation(i, 0, count);
                }
                else if (arr[i, 1] == arr[a, 0])
                {
                    Relation(i, 1, count);
                }
            }
            visit[arr[a, 0]] = false;
        }
        else
            return;
    }

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

문제

문제

출처

ICPC

시간초과가 나는데 시간을 어떻게 줄여야 할 지 모르겠습니다(C#)

wjddn7118 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말