글 읽기 - 시간초과..

moyoungmin 5년 전 0

혹시 이 문제를 dfs나 bfs가 아닌 트리로 풀 수는 없나요?

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

class node {
public:
	int value;
	node * parent;
	vector <node *> children;
public:
	node(int);
};

node::node(int value) {
	this->value = value;
	parent = NULL;
}

class tree {
public:
	node * root;
	vector <node *> list; // 탐색 용도로 사용.
public:
	tree(int value) {
		node * newNode = new node(1);
		root = newNode;
		list.push_back(newNode);
	}
	bool insertNode(int parent, int child) {
		int length = list.size();
		for (int i = 0; i < length; i++) {
			if (parent == list[i]->value) {
				node * newNode = new node(child);
				newNode->parent = list[i];
				list[i]->children.push_back(newNode);
				list.push_back(newNode);
				return true;
			}
		}
		return false;
	}
	void print(int num) {
		int length = list.size();
		for (int i = 0; i < length; i++) {
			if (num == list[i]->value) {
				printf("%d\n", list[i]->parent->value);
			}
		}
	}
};

int main() {
	tree t(1);
	int count, num1, num2;
	scanf("%d", &count);
	for (int i = 1; i < count; i++) {
		scanf("%d %d", &num1, &num2);
		if (!t.insertNode(num1, num2)) {
			t.insertNode(num2, num1);
		}
	}
	for (int i = 2; i <= count; i++) {
		t.print(i);
	}
}

djm03178 5년 전 0

dfs bfs는 탐색 방법을 말하는 거고 트리는 그래프의 형태를 말합니다. dfs bfs도 결국 다 트리에서 이루어지는 겁니다.

그리고 이 문제는 루트부터 차례대로 그에 연결된 원소가 주어지는 것이 아니라, 임의의 순서로 주어지기 때문에 지금과 같이 풀면 안 됩니다. 즉, 아직 루트에 연결이 안 된 두 노드 쌍이 입력으로 들어올 수 있습니다. 이런 문제는 정점간의 연결 상태를 우선 다 저장해 둔 뒤에, 루트 노드부터 전체를 탐색하는 방법으로 트리를 구성해야 합니다.

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

문제

문제

출처

ICPC

시간초과..

moyoungmin 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말