(100YEARSWAR) 미치겠습니다. 시간 초과가 뜨는데 이유를 모르겠습니다. (소스 첨부...)

  • somebodil
    somebodil
    #include <stdio.h>
    
    const int FRANCE_KING = 0;
    const int ENGLAND_KING = 1;
    
    struct Surbordinate
    {
        Surbordinate(int value_, Surbordinate* next_) : next(next_), value(value_) {}
        int value;
        Surbordinate* next;
    };
    
    class Surbordinates
    {
    public:
        Surbordinates()
        {
            Head = NULL;
        }
    
        void add(int value)
        {
            if(Head == NULL)
            {
                Head = new Surbordinate(value, NULL);
            }
            else
            {
                Surbordinate* current = Head;
                while(current->next != NULL)
                    current = current->next;
    
                Surbordinate* newNode = new Surbordinate(value, NULL);
                current->next = newNode;
            }
        }
    
    public:
        Surbordinate* Head;
    };
    
    struct Lord
    {
        Lord() { side = -1; myLord = -1; }
        Surbordinates surbordinates;
        int myLord;
        int side;
    };
    
    void changeLord(Lord* lordary, int n)
    {
        if(lordary[n].side == ENGLAND_KING)
        {
            lordary[n].side = FRANCE_KING;
        }
        else
        {
            lordary[n].side = ENGLAND_KING;
        }
    
        Surbordinate* current = lordary[n].surbordinates.Head;
        while(current != NULL)
        {
            changeLord(lordary, current->value);
            current = current->next;
        }
    }
    
    int main()
    {
        //태스트 케이스 T
        int testNum = 0;
        scanf("%d", &testNum);
    
        while(testNum-- > 0)
        {
            //귀족의 수 N입력
            int aristocratNum = 0;
            scanf("%d", &aristocratNum);
    
            //질문의 개수 Q입력
            int questionNum = 0;
            scanf("%d", &questionNum);
    
            //귀족의 수 만큼 배열 할당
            Lord* lordAry = new Lord[aristocratNum];
    
            //귀족의 군종관계 입력
            //각 나라의 왕은 입력하지 않기때문에 -2만큼...
            for(int i=0; i<aristocratNum-2; ++i)
            {
                int a,b;
                scanf("%d %d", &a, &b);
    
                lordAry[a-1].surbordinates.add(b-1);
                lordAry[b-1].myLord = a-1;
            }
    
            //영국과 프랑스로 팀을 나눈다
            for(int i=0; i<aristocratNum; ++i)
            {
                switch(i)
                {
                case 0:
                    lordAry[i].side = FRANCE_KING;
                    break;
                case 1:
                    lordAry[i].side = ENGLAND_KING;
                    break;
                default:
                    {
                        int myLord = i;
                        while(!(myLord == ENGLAND_KING || myLord == FRANCE_KING))
                        {
                            myLord = lordAry[myLord].myLord;
                        }
                        lordAry[i].side = myLord;
                    }
                    break;
                }
            }
    
            //질문을 받으면서 팀을 변경한다
            //귀족이 나라를 배신했을때 그 아랫 귀족까지 배신되도록
            //재귀를 이용한다.
            for(int i=0; i<questionNum; ++i)
            {
                char c;
                getchar();
                scanf("%c", &c);
                switch(c)
                {
                case 'T':
                    {
                        int n;
                        scanf("%d", &n);
    
                        //재귀 사용
                        changeLord(lordAry, n-1);
                    }
                    break;
                case 'Q':
                    {
                        int a,b;
                        scanf("%d %d", &a, &b);
                        if(lordAry[a-1].side == lordAry[b-1].side)
                        {
                            printf("Ally\n");
                        }
                        else
                        {
                            printf("Enemy\n");
                        }
                    }
                    break;
                }
            }
        }
    }
    

    위에와 같이 했고, 예제 답 혹은 그 이상으로 저만의 테스트 데이터를 만든 후에 검증을 해봤지만 다 알맞게 나왔습니다. 하지만 계속해서 시간초과라고 뜨고 답답합니다.

    5시간 현재 붙잡고있습니다.

    어디서 문제인지 힌트라고 주시면 정말 감사하겠습니다. ㅠㅠ

    100YEARSWAR 문제를 제가 풀어보려고 노력한것입니다.

    댓글의 조언에 따라 위에 코드 주석 하나하나 달았습니다.

    코드 설명입니다.

    전체 귀족 수 크기의 배열을 생성합니다.
    각 원소들은 해당 귀족과 일치합니다.
    0은 프랑스왕이며 1은 영국왕입니다.
    각 원소는 Lord(영주)라는 구조체로 만들어져있는데,
    자기 직속 휘하 귀족이 몇명있는지를 알수 있습니다.
    (Subordinate 변수, 링크드 리스트를 이용한다.)
    또한 각각의 직속 상관 귀족이 누구인지도 알 수 있습니다. (myLord 변수)
    예를 들어 예제에서
    1 3
    2 4
    3 5
    이면 1의 직속 휘하 귀족은 3이며 3의 직속 휘하 귀족은 5입니다.
    또한 3의 직속 상관 귀족은 1입니다.

    각각의 원소는 side라는 변수로 영국 혹은 프랑스국 동맹국인지 알 수 있습니다.

    changeLord를 통해서 재귀를 통해 반란된것을 표시합니다.
    예를 들어 T 3을 하면 귀족 3 및 3의 포함된 모든 귀족은 자기 국가를 바꿉니다. (not과 같이)

    이런식으로 했는데 되지 않습니다. ㅠㅠ
    또 설명해드릴부분 있는지 알려주시면 상세히 알려드리겠습니다.

    부탁드립니다. ㅠㅠ


    8년 전
7개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    소스코드 정리 부탁드리고요
    어느문제인지는 알려주시기 바랍니다.
    그리고 어떻게 풀었는지도 설명해야 답변이 가능합니다


    8년 전 link
  • somebodil
    somebodil

    글 수정했습니다. 최대한 상세히 쓴다고 썻는데 조금 허접할 수 있습니다. 잘부탁드립니다. ㅠ


    8년 전 link
  • kcm1700
    kcm1700

    관리자의 권한으로 멋대로 소스코드 formatting 했습니다. 다음에 소스코드를 올릴 때는 밑의 도움말 반드시 참고하셔서 소스코드가 정상적으로 보이도록 해주세요.

    이 문제는 사용하신 알고리즘으로는 제한시간 내에 통과할 수 없습니다. 사용하신 알고리즘의 시간복잡도 분석을 간단히 해보시면 데이터에 따라 최악의 경우 O(Q * N) 시간이 걸리고 제한 시간 내에 통과하기에는 너무 연산량이 많을거라 추측할 수 있습니다.

    이 문제는 더 빠른 시간에 해결 가능한 알고리즘이 존재합니다.


    8년 전 link
  • somebodil
    somebodil

    감사합니다. 다시한번 해보겠습니다!


    8년 전 link
  • somebodil
    somebodil

    고수님들 혹시 힌트좀 주시면 안되나요...? ;;;;;;;;;;


    8년 전 link
  • hyunhwan
    hyunhwan

    Coders high 2013 페이지를 참고해보시길 바랍니다.


    8년 전 link
  • Kureyo
    Kureyo

    일단 드리고싶은 말씀은 이 문제가 단순 구현 문제는 아니라는 점입니다.

    각 쿼리에 대해 lg N시간에 풀수있는 자료구조가 떠오르지않는다면
    위 링크를 참조해보세요


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.