[11725] C++ : 트리의 부모 찾기

[11725] C++ : 트리의 부모 찾기
/category/Computer%20Science/Baekjoon

2022. 8. 15. 01:32

이번 문제는 트리를 연습하기 위해 가져온 문제이다. 하지만.. 풀다보니 트리가 아니라 그래프 형식으로 만들어야한다는 걸 깨달은 문제이기도 하다.

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이

처음에 이 문제를 읽었을 때 이해가 안되었다.

이렇게 트리를 그리는 것은 성공했는데 출력 결과가 내가 생각한 것과 조금 달랐다. 다시 문제를 읽어보니 '부모 노드 번호를 2번 노드부터 순서대로 출력한다.' 라고 적혀있었다. 즉, 2가 저장된 노드부터 3,4,5 ... 순서대로 부모 노드를 출력하는 것이었다. 문제 이해부터 조금 시간이 걸렸다.

문제 이해를 한 뒤 나는 이걸 이진트리로 구현해서 할 생각을 했다. 왜냐하면 예제가 모두 이진트리였기 때문에 일반적인 트리라고 생각을 못했다. 그래서 구조체로 leftchild, rightchild를 만들었다.

typedef struct node{
	int data;
	struct node* link;
}Node;


void link(Node*p, Node *c, int data)
{
	p->link = c;
	c->data = data;
	c->link = NULL;
}

그런데 main함수를 만들면서 생각난것이 문제의 그 어느 곳에도 binary tree라는 조건이 없었다. 그래서 이런 접근은 불가능하다는 것을 알았다. 그럼 자식노드가 여러개인 tree를 만들어야했다.

근데 노드의 개수를 알 수 없는 트리를 만드려고 하니 머리가 아팠다. 그래서 두번째로 생각해낸 것이 트리를 만들지 말고 배열에 부모 노드를 기록하는 형식으로 코드를 작성했다.

#include<iostream>


using namespace std;


int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	int number;
	cin >> number;
	
	int* arr = (int*)calloc(sizeof(int),(number+1));
	
	for (int i = 1; i < number; i++)
	{
		int n1, n2;
		cin >> n1 >> n2;

		if (n1 == 1)
			arr[n2] = 1;
		else if (n2 == 1)
			arr[n1] = 1;
		else if (arr[n1] != 0)
			arr[n2] = n1;
		else
			arr[n1] = n2;
	}

	for (int i = 2; i <= number; i++)
		cout << arr[i] << "\n";

}

예제는 잘 작동되었다. 근데 백준에 입력하니 이상하게도 오답처리가 되었다. 다시 한번 더 문제를 보니 내 풀이 방식에 큰 오류가 있었다. 예제는 루트 노드에 노드를 하나씩 붙여나가는 형식만 소개가 되어있었다. 위 코드는 완전 상관없는 노드가 등장했을 때 작동이 되지 않았다.

예를 들어 예제 입력1에서 순서를 바꿔 아래의 상황이 된다고 가정하자.

이렇게 된다면 5가 제대로 실행이 안된다.

그 이유는 하나씩 붙여가다 보면 위와 같은 상황이 발생하기 때문이다. 처음에 3은 5를 가리키게 되고 마지막에 6과 3이 입력된다. 내가 짠 코드를 기준으로 하면

else if (arr[n1] != 0)
	arr[n2] = n1;

이 부분에 걸리게 되는데 이것을 실행하면 3이 6을 가리키게 되고 끝이 나버린다. 결국 5는 트리에 연결되지 못한다.

이 문제를 해결하기 위해 배열을 이리저리 처리해보았지만 계속 오답이 나왔고 이런 방식으로는 결코 문제를 풀 수 없다는 것을 느꼈다.

루트노드부터 입력되는 것이 아니기 때문에 트리 형태로 입력을 받을 수 없었다. 그래서 생각한 것이 무방향 그래프로 입력을 받는 것이다. 사실 트리는 그래프의 특수한 경우 중 하나이기 때문에 결국은 그래프이다.

n이 100000까지 가능하기 때문에 인접행렬은 사실상 못쓴다고 생각하고 인접리스트로 문제를 해결했다. C++에서 linked list를 구현할 때에는 vector를 사용하면 된다고 해서 vector를 사용했다.

//main 내부
    queue<int> q;
	cin >> n;
	vector<int> *tree = new vector<int>[n+1];
	

	//결국 tree도 그래프의 일종이기 때문에 그래프를 생성하는 방식으로 만들어준다. 
	for (int i = 1; i < n; i++)
	{
 		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

이렇게 짠 코드에 예제 입력 1번을 적용시키면 다음과 같이 나온다.

이렇게 트리를 정상적으로 만들었으면 남은 문제는 어떻게 부모 노드를 기록해둘까라는 것이다. 그래프를 사용하는 것이라서 오랜만에 자료구조 책을 꺼내 그래프 파트를 정독하니 bfs, dfs가 눈에 띄었다. 확실한건 데이터 하나하나 접근해서 부모 노드를 기록해주어야 하기 때문에 탐색을 사용해야한다.

둘 다 큰 차이는 없다고 생각이 들었는데 루트노드가 1인 것을 알고 있고 각 노드의 부모를 찾는거니 bfs가 더 유리하지 않을까라는 생각이 들었다. 그래서 bfs를 구현했다.

bfs는 queue를 이용해서 제작하면 된다.

queue<int> q;
bool visited[100001] = { false };
	visited[1] = true;


	q.push(1);

	while (!q.empty())
	{
		int front = q.front();
		q.pop();

		for (int i = 0; i < tree[front].size(); i++)
		{
			if (!visited[tree[front][i]])
			{
				q.push(tree[front][i]);
				visited[tree[front][i]] = true;
				parent[tree[front][i]] = front;
			}
		}
	}

visited는 방문했는지에 대한 여부를 알려준다. bfs에 대한 자세한 설명은 나중에 한번 알고리즘 게시판에 정리해서 올리겠다. 지금은 귀찮다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main()
{
	cin.tie(NULL);
	cin.sync_with_stdio(false);

	int n, a, b;
	int parent[100001] = { 0 };
    bool visited[100001] = { false };
    queue<int> q;
    
	cin >> n;
	vector<int> *tree = new vector<int>[n+1];
	
	for (int i = 1; i < n; i++)
	{
 		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}


	visited[1] = true;


	q.push(1);

	while (!q.empty())
	{
		int front = q.front();
		q.pop();
		for (int i = 0; i < tree[front].size(); i++)
		{
			if (!visited[tree[front][i]])
			{
				q.push(tree[front][i]);
				visited[tree[front][i]] = true;
				parent[tree[front][i]] = front;
			}
		}
	}

	for (int i = 2; i <= n; i++)
		cout << parent[i] << endl;

	return 0;

}

그래서 이런 코드를 작성했는데 시간초과가 발생했다. 인접리스트를 이용한 bfs는 시간복잡도가 O(n+e)라서 시간 초과가 날 이유가 없는데 왜 일어나는지 계속 찾아보았다.

알고보니 굉장히 단순하게 endl 때문에 시간을 잡아먹고 있었다. endl -> \n으로 바꾸면 해결!

<최종코드>

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main()
{

	cin.tie(NULL);
	cin.sync_with_stdio(false);

	int n, a, b;
	int parent[100001] = { 0 };
	int count = 0;
	queue<int> q;
	cin >> n;
	vector<int> *tree = new vector<int>[n+1];
	

	//결국 tree도 그래프의 일종이기 때문에 그래프를 생성하는 방식으로 만들어준다. 
	for (int i = 1; i < n; i++)
	{
 		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}

	bool visited[100001] = { false };
	visited[1] = true;


	q.push(1);

	while (!q.empty())
	{
		int front = q.front();
		q.pop();

		for (int i = 0; i < tree[front].size(); i++)
		{
			if (!visited[tree[front][i]])
			{
				q.push(tree[front][i]);
				visited[tree[front][i]] = true;
				parent[tree[front][i]] = front;
				count++;
			}
		}
		if (count == n-1)
			break;
	}

	for (int i = 2; i <= n; i++)
		cout << parent[i] << "\n";

	return 0;

}

저작자표시

'Computer Science > Baekjoon' 카테고리의 다른 글

[1927] C++ : 최소 힙 (0)	2022.08.16
[24444] C++ : 알고리즘 수업 - 너비 우선 탐색 1 (0)	2022.08.15
[10866] C++ : 덱 (0)	2022.08.14
[18528] C++ : 큐 2 (0)	2022.08.14
[10828] C++ : 스택 (0)	2022.08.14

모북의 코딩블로그

CATEGORIES