-
문제조건
- 루트 없는 트리 → Graph가 생각나는 형태.
- Root가 없는 트리이지만, Root를 1이라고 정하는 경우, 각 노드의 부모를 구하는 프로그램.
- 일단 여기서는 "트리에서의 Search"개념이 필요하다.고 생각했는데, 보니까 graphp에서의 search문제에 가까운 듯한 느낌이 들어서 BFS를 사용했다.
- 출력으로는 "각 노드의 부모 번호"를 "2번 노드"부터 순서대로 출력해야 한다.
- 현재 이 트리는 어떤 Rule이 있는 것이 아니라서, Tree에서의 Searh라 생각하고 접근 시 시간이 더 오래 걸릴 것 같았다.
-
생각 과정
- 따라서 Graph방식으로의 접근이 가장 먼저 떠올랐다.
- DFS 또는 BFS로 child를 search해보기로 했다. 그런데 그러기 위해서는 child node가 부모에 대한 pointer정보를 가지고 있어야 하는걸까???
- 입력으로는 단순히 Graph가 주어진다... "1번"노드를 root 노드로서, 1번에서부터 child로 search를 진행해가는 식으로 하면 되는데, BFS로 하는게 좋지 않을까 생각했다. 왜냐하면, BFS는 한 번에 현재의 모든 "child 노드"들에 대한 처리를 할 수가 있으니까.
- 매 숫자를 찾느라 매번 DFS 또는 BFS를 하면 비용이 커질 것. 따라서, search를 하면서 vector에 저장하는 방식을 생각 할 수 있다.
- 그런데 "입력"으로 단순히 Graph가 주어지게 되는것이라면, 어떻게 부모를 알 수 있을까? → 내 생각에는, Search과정에서 BFS의 경우라면, child를 Queue에다가 push를 하게 되는데, 이 때, "이 노드" 의 child노드들일 테니, 이 child노드에 대한 parent는 "이 노드"다 라고 등록을 해 주도록 한다.
- 근데 그래서 또 한가지 의문이 들었는데, Graph모양이라면, parent가 여러 개 인 경우도 생길 수 있는걸까??? 아니, 그러면 문제를 풀 수가 없지 않나.. 내 생각에는, "자식은 여러개 O" 하지만 "부모는 여러개일 수 X" 그런 입력을 주어질 것 같다. 예제 입력은 그랬다.
- 따라서 Graph방식으로의 접근이 가장 먼저 떠올랐다.
-
따라서 필요한 것.
- BFS를 하기 위해, 나는 "인접행렬"말고 "인접 리스트"를 사용할 거임. 따라서 노드개수만큼의 vector들이 필요하다. : vector graph[NODE_SIZE]
- BFS를 하기 위해, queue자료구조가 필요하다. : 단순한 Queue 가 필요하다.
- visit array가 필요한가? - Tree가 아닌 graph라면 필요할 것. But, Tree라면 parent노드가 여러개가 아닌 상황이라면 visit array가 필요하지 않을 듯. <하지만 일단 visit array도 사용해 보고, 정상적으로 작동한다면 빼고나서도 정상작동하는지 확인 해 보도록 하자.> < 아 생각해보니 Undirected graph 정보로서 , edge정보를 처음에 받게 되기 때문에, v1,v2의 인접리스트 각각에 v2,v1이 추가되는 것이기 때문에, visit정보가 필요할 수도 있겠다)
- 각 노드의 parent노드를 저장하기 위해서 노드사이즈의 vector : vector whoisparent;
7
1 6
6 3
3 5
4 1
2 4
4 74
6
1
3
1
4#include <iostream>
#include <vector>
#include <queue>
// 2 <= N <= 10,0000
using namespace std;
int n;
vector<int> graph[100001];
queue<int> q;
int visit[100001];
int whoisparent[100001];
void bfs(int start)
{
int cur;
q.push(start);
while (q.empty() == false) {
cur = q.front();
q.pop();
// Check child nodes : <1. parent node = cur node>
for (int i = 0; i < graph[cur].size(); i++)
{
int temp_child = graph[cur][i];
// if this child has not been visited , progress these
if (!visit[temp_child]) {
whoisparent[temp_child] = cur; // assign cur node as parent node of this temp_child node.
q.push(temp_child); // push this temp_child node into the queue.
visit[temp_child] = 1;
}
}
}
}
int main()
{
cin >> n; // get the number of node
// get the edge info (개수 : n-1개의 정보가 주어진다)
// Undirected 이네
for (int i = 0; i < n - 1; i++)
{
int v1, v2;
cin >> v1 >> v2;
graph[v1].push_back(v2);
graph[v2].push_back(v1);
}
bfs(1);
for (int i = 2; i <= n; i++)
{
printf("%d\n", whoisparent[i]);
}
}아무래도 Tree 개념이 전혀 생각이 안나서 Tree 이론 공부를 2월 안에 해야할 것 같다.
Graph문제만 너무 풀었다. 이 문젠 이름은 Tree였으나 결국 graph접근법으로 푸는 문제였네..
