글 읽기 - ..고수님들 반례좀 찾아주시면 감사하겠습니다..

tjdvyzl12 2년 전 0

예제는 문제없이 출력되구요..

리프노드에 도달하면 그 노드의 깊이를 구해서 cnt에 추가해줌으로써

cnt가 짝 홀에 따라 No Yes 출력 하게 했습니다..ㅠㅠㅠ 근데 자꾸 틀렸다고하네요..

#include <iostream>
#include <vector>
using namespace std;

int cnt = 0;

class Node {
public:
	Node* parent;
	vector<Node*> child_v;
	int data;
	Node(int data):data(data),parent(nullptr){}
};

class Tree {
public:
	Node* root;
	vector<Node*> node_v;
	Tree(int data) {
		Node* node = new Node(data);
		root = node;
		node_v.push_back(node);
	}

	void insert(int a, int b) {	
		for (int i = 0; i < node_v.size(); i++) {
			if (node_v[i]->data == a) {
				Node* node = new Node(b);
				node_v[i]->child_v.push_back(node);	
				node->parent = node_v[i];
				node_v.push_back(node);
				break;
			}
			if (node_v[i]->data == b) {
				Node* node = new Node(a);
				node_v[i]->child_v.push_back(node);
				node->parent = node_v[i];
				node_v.push_back(node);
				break;
			}
		}
	}

	void preorder(Node* node) {
		if (node == nullptr) return;
		cout << node->data << " ";
		for (int i = 0; i < node->child_v.size(); i++) {
			preorder(node->child_v[i]);
		}
		
	}

	int getDepth(Node* node, int depth) {
		if (node == nullptr) return depth;
		if (node == root) return depth;
		return getDepth(node->parent, depth + 1);
	}

	void order(Node* node) {
		if (node == nullptr) return;
		else {
			if (node->child_v.size() == 0) {
				cnt += getDepth(node, 0);
			}
			for (int i = 0; i < node->child_v.size(); i++) {
				order(node->child_v[i]);
			}
		}
	}
};

int main() {
	Tree tree(1);
	int n; cin >> n;
	for (int i = 0; i < n-1; i++) {
		int a, b;
		cin >> a >> b;
		tree.insert(a, b);
	}
	tree.order(tree.root);
	if (cnt % 2 == 0) cout << "No";
	else cout << "Yes\n";

	return 0;
}

dps2 2년 전 1

63번째 줄에서 +1을 더 해주셔야 답이 나옵니다.

그런데 수정하시더라도 시간초과가 뜰 것입니다.

그 이유는 insert하실때 원소를 하나하나 보기 때문에 O(n)시간 복잡도가 걸리며

n개를 넣기 때문에 O(n^2)이여서 시간이 너무 오래걸립니다.

또한 연결정보를 줄때 이미 루트와 연결되어있는 노드끼리의 연결정보를 준다는 보장이 없습니다.

예를 들어 노드의 수가 8개 인데

5 6을 먼저 줄 가능성이 있습니다.

또한 depth를 계산할때 루트까지 올라가는데 order에서 current depth를 넘긴다면

별다른 계산 없이 바로 구할 수 있습니다.

질문자님 코드 마개조해서 올려드립니다.

주석보시고 이해안되시는 부분있으면 댓글남겨주세요

#include <iostream>
#include <vector>
#include <set>

using namespace std;

class Node {
    public:
    void addConnection(int which){//두 노드를 연결시키는 메소드
        this->connections.insert(which);
    }
    int totalDepth(Node*nodes,int currentDepth){
        if(this->isVisited)//이전에 방문했다->(parent임)
            return 0;
        this->isVisited = true;
        int total=0;
        for(set<int>::iterator iter = this->connections.begin();iter!=this->connections.end();iter++)
            total+=nodes[*iter].totalDepth(nodes,currentDepth+1);
        //이어져 있는 모든 노드들로 부터 갈 수 있는 리프노드의 depth합을 다 더함
        return total == 0 ? currentDepth : total;
        //total이 0이면 자기 자신이 leaf이므로 현재 depth를, 그렇지 않다면 total을 리턴
    }
    Node(bool isVisited = false):isVisited(isVisited){}
    private:
    bool isVisited;//방문했는지 여부(양방향으로 connection을 넣을 것이여서 필요함)
    set<int> connections;//어느 노드들과 연결되어있는지
};

int main() {
	int n;
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    Node *nodes = new Node[n+1];//노드들을 선언
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
        nodes[a].addConnection(b);//연결해주기
        nodes[b].addConnection(a);
	}
	if (nodes[1].totalDepth(nodes,0) % 2 == 0)//1번으로부터 totalDepth를 계산
        cout << "No\n";
	else
        cout << "Yes\n";
	return 0;
}

tjdvyzl12 2년 전 1

감사합니다 ㅠㅠㅠ 더 분발할게요

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

문제

문제

출처

ICPC

..고수님들 반례좀 찾아주시면 감사하겠습니다..

tjdvyzl12 2년 전 0

dps2 2년 전 1

tjdvyzl12 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말