글 읽기 - 틀렸다고 나오는 이유를 모르겠습니다

hglim4747 8년 전 0

입력예제를 직접 만들어서 실행시켰을 때 기대한 값이 항상 나옵니다.
무엇이 문제일까요ㅠㅠ 수십번을 해보았습니다! 도와주세요
#include <iostream>
#include <list>
#include <time.h>
using namespace std;
 
class Node
{
public:
    Node(){}
    Node(int n1, int n2, int n3)
    {
        n[0] = n1; n[1] = n2; n[2] = n3;
        child[0] = NULL; child[1] = NULL;
        parent = NULL;
 
        //static int a = 0;
        //index = a++;
    }
 
    int n[3];
    //int index;
    Node *child[2];
    Node *parent;
};
 
int n;
list<Node*> input, tree;
list<Node*>::iterator tree_iter;
void Input();
 
Node* SearchEnemy(Node *tree, Node *p);
bool IsGame(Node* s1, Node *s2);
Node** Eat(Node* s1, Node *s2);
 
int main()
{
    Input();
    while (!input.empty())
    {
        Node *each_input = input.front();
        input.pop_front();
 
        bool inserted = false;
        for (tree_iter = tree.begin(); tree_iter != tree.end();)
        {
            Node *each_tree = *tree_iter;
            tree_iter = tree.erase(tree_iter); // 우선 트리를 빼냄
 
            bool isRoot;
            Node *enemy = SearchEnemy(each_tree, each_input); // 현재 트리에서 적(먹이사슬 관계가 있는 놈) 찾기, 배부른 놈은 제외됨
            isRoot = (enemy == each_tree); // 먹이관계와 먹이사슬인가?
 
            if (enemy == NULL) // 적이 없으면 트리에 들어가지 못함 => 다음 트리와 비교
            {
                tree.push_front(each_tree); // 앞에다 넣음으로써 재탐지를 막음
                continue;
            }
 
            Node **sorted = Eat(enemy, each_input); // 싸워서 쌘놈이 앞으로 온 배열을 받음 (무조건 싸움의 결과가 나옴)
            Node *winner = sorted[0];
            Node *loser = sorted[1];
 
            //cout << winner->index << "이(가) " << loser->index << "을(를) 먹음" << endl; // 디버깅용 앞에놈이 뒤에놈을 먹음
            if (loser->parent != NULL) // 이긴놈이 트리 중간에 끼어들어갈 때 winner가 loser의 child자리를 먹음
            {
                winner->parent = loser->parent;
                for (int i = 0; i < 2; i++)
                {
                    if (winner->parent->child[i] == loser)
                    {
                        winner->parent->child[i] = winner;
                    }
                }
            }
            loser->parent = winner;
            for (int i = 0; i < 2; i++)  // winner는 배고픈 상태임 (무조건 자식노드가 들어갈 자리가 있음)
            {
                if (winner->child[i] == NULL)
                {
                    winner->child[i] = loser;
                    break;
                }
            }
            inserted = true;
 
            if (isRoot) // 왕권다툼(?) 이었다면
            {
                tree.push_back(winner); // 이긴놈이 트리의 루트가 됨
                //cout << "New King : " << winner->index << endl;
            }
            else
            {
                tree.push_back(each_tree);  // 그냥 원상복귀
            }
            break;
        }
 
        if (!inserted)
        {
            tree.push_back(each_input);
        }
    }
 
    int output = tree.size();
    cout << output; // 트리의 갯수가 정답
    return 0;
}
 
Node* SearchEnemy(Node *tree, Node *p)
{
    if (tree == NULL) return NULL;
 
    if (IsGame(tree, p))
        return tree;
 
    Node *t = NULL;
    for (int i = 0; i < 2; i++)
    {
        t = SearchEnemy(tree->child[i], p);
        if (t) return t;
    }
 
    return NULL;
}
 
bool IsGame(Node* s1, Node *s2)
{
    for (int i = 0; i < 3; i++)
    {
        if (s1->n[i] < s2->n[i]) break;
        if (i == 2 && (s1->child[0] == NULL || s1->child[1] == NULL)) // 이긴 상어 s1이 배가 불러있으면 안됨
        {
            return true;
        }
    }
    for (int i = 0; i < 3; i++)
    {
        if (s1->n[i] > s2->n[i]) break;
        if (i == 2 && (s2->child[0] == NULL || s2->child[1] == NULL)) // 이긴 상어 s2가 배가 불러있으면 안됨
        {
            return true;
        }
    }
    return false;
}
 
Node** Eat(Node* s1, Node *s2)
{
    Node **t = new Node*[2];
    t[0] = NULL; t[1] = NULL;
    for (int i = 0; i < 3; i++)
    {
        if (s1->n[i] < s2->n[i]) break;
        if (i == 2)
        {
            t[0] = s1;
            t[1] = s2;
        }
    }
    for (int i = 0; i < 3; i++)
    {
        if (s1->n[i] > s2->n[i]) break;
        if (i == 2)
        {
            t[0] = s2;
            t[1] = s1;
        }
    }
    return t;
}
 
void Input()
{
    //n = 5;
    //input.push_back(new Node(4, 5, 5));
    //input.push_back(new Node(10, 10, 8));
    //input.push_back(new Node(5, 7, 10));
    //input.push_back(new Node(8, 7, 7));
    //input.push_back(new Node(8, 10, 3));
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        input.push_back(new Node(a, b, c));
    }
 
    //srand((unsigned)time(NULL));
    //n = rand() % 10;
    //for (int i = 0; i < n; i++)
    //{
    //  int a = rand() % 10;
    //  int b = rand() % 10;
    //  int c = rand() % 10;
    //  cout << "input " << i << " : " << a << " " << b << " " << c << endl;
    //  input.push_back(new Node(a,b,c));
    //}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

틀렸다고 나오는 이유를 모르겠습니다

hglim4747 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
