알고리즘 기술
링크드 리스트 2
헐랭미
2020. 7. 15. 14:51
https://jaeyoon8783.tistory.com/6?category=876641
링크드 리스트
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69..
jaeyoon8783.tistory.com
여기에서 링크드 리스트의 기본을 배웠다. 그런데
https://www.acmicpc.net/problem/11725
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
트리를 DFS 탐색하는 과정에서 문제가 하나 발생했다.
go 함수(DFS 탐색) 중에 list를 다시 참조해야 하는데 list배열이 class List 위에 있으면 만들수가 없고 밑에 있으면 go함수가 참조 못하는 현상이 벌어진다.
밑의 코드가 이런 예시이다. 안 돌아갈것이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <iostream>
#include <vector>
#include <algorithm>
#define pii pair<int, int>
using namespace std;
int parent[100001];
class node
{
public :
int data;
node* next;
};
class List
{
public :
node* head = NULL;
node* tail = NULL;
void init(List l)
{
node* tmp = l.head;
while (tmp != NULL)
{
head = tmp->next;
delete tmp;
tmp = head;
}
delete head;
}
void add(int data)
{
node* nnode = new node;
nnode->data = data;
nnode->next = NULL;
if (head == NULL)
head = nnode;
else
tail->next = nnode;
tail = nnode;
}
void go(int cur, int p)
{
parent[cur] = p;
node* tmp = head;
while (tmp != NULL)
{
if (tmp->data != p)
l[tmp->data].go(tmp->data, cur);
tmp = tmp->next;
}
}
};
List l[100001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
int a, b;
for (int i = 0; i < n-1; i++)
{
cin >> a >> b;
l[a].add(b);
l[b].add(a);
}
l[1].go(1, 0);
for (int i = 2; i <= n; i++)
cout << parent[i] << '\n';
}
|
cs |
그래서 List 배열과
add, init, go 함수를 따로 나눠줘야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#define pii pair<int, int>
using namespace std;
int parent[100001];
class node
{
public :
int data;
node* next;
};
class List
{
public :
node* head = NULL;
node* tail = NULL;
};
List list[100001];
void init(List list)
{
node* tmp = list.head;
while (tmp != NULL)
{
list.head = tmp->next;
delete tmp;
tmp = list.head;
}
delete list.head;
}
void add(int list_num, int data)
{
node* nnode = new node;
nnode->data = data;
nnode->next = NULL;
if (list[list_num].head == NULL)
list[list_num].head = nnode;
else
list[list_num].tail->next = nnode;
list[list_num].tail = nnode;
}
void go(int list_num, int cur, int p)
{
parent[cur] = p;
node* tmp = list[list_num].head;
while (tmp != NULL)
{
if (tmp->data != p)
go(tmp->data, tmp->data, cur);
tmp = tmp->next;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
int a, b;
for (int i = 0; i < n-1; i++)
{
cin >> a >> b;
add(a, b);
add(b, a);
}
//l[1].go(1, 0);
go(1, 1, 0);
for (int i = 2; i <= n; i++)
cout << parent[i] << '\n';
}
|
cs |
이렇게 말이다.
20/08/20 추가..
인줄 알았는데 훨씬 더 간단하게 굳이 함수를 쓰지 않아도 되는것이였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <iostream> #define pii pair<int, int> using namespace std; class node { public : int data; node* next; }; class Edge { public : node* head = NULL; node* tail = NULL; void insert(int d) { node* nnode = new node; nnode->data = d; nnode->next = NULL; if (head == NULL) head = nnode; else tail->next = nnode; tail = nnode; } }; Edge edge[100001]; int ans[100001]; void go(int cur, int parent) { ans[cur] = parent; node* tmp = edge[cur].head; while (tmp != NULL) { if (tmp->data != parent) go(tmp->data, cur); tmp = tmp->next; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,a,b; cin >> n; for (int i = 0; i < n - 1; i++) { cin >> a >> b; edge[a].insert(b); edge[b].insert(a); } go(1, 0); for (int i = 2; i <= n; i++) cout << ans[i] << '\n'; } | cs |