재귀 호출 이용해서 문제 푸는데
자식이 2개 이상일 때 뭘 해도 답이 이상하게 나와서 블로그 참고 했습니다
백준# 1967 - 트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의..
programming-mr.tistory.com
감사감사
using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;
namespace _1967
{
public class Node
{
public static int result=0;
public int num;
public int value;
public List<Node> childList;
public int distance;
public Node target;
public Node(int num, int value)
{
this.num = num;
this.value = value;
this.childList = new List<Node>();
}
public void AppendChild(Node node)
{
this.childList.Add(node);
}
public void FindDistance()
{
if(this.childList.Count ==0)
{
this.distance = 0;
}
else if(this.childList.Count==1)
{
this.childList[0].FindDistance();
this.distance = this.childList[0].distance + this.childList[0].value;
if(this.distance >= Node.result)
{
Node.result = this.distance;
}
}
else
{
foreach(var child in this.childList)
{
child.FindDistance();
}
var list = this.childList.OrderByDescending(x => x.distance + x.value).ToList();
if(list[0].distance+list[0].value+list[1].distance+list[1].value > Node.result)
{
Node.result = list[0].distance + list[0].value + list[1].distance + list[1].value;
}
this.distance = list[0].distance + list[0].value;
}
}
}
class Program
{
static void Main(string[] args)
{
List<Node> nodeList = new List<Node>();
Node root = new Node(1,0);
nodeList.Add(root);
int nodeCount = Int32.Parse(Console.ReadLine());
for(int i=0; i<nodeCount-1; i++)
{
string[] input = Console.ReadLine().Split(' ');
int pNodeNum = int.Parse(input[0]);
int cNodeNum = int.Parse(input[1]);
int nodeValue = int.Parse(input[2]);
Node pNode = nodeList.Find(x => x.num == pNodeNum);
Node newNode = new Node(cNodeNum, nodeValue);
pNode.AppendChild(newNode);
nodeList.Add(newNode);
}
root.FindDistance();
Console.WriteLine(Node.result);
}
}
}
------------------------------------------------------------------------------------------
1967번: 트리의 지름
파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 ��
www.acmicpc.net
트리를 먼저 만들었다.
Node 클래스를 하나 만들고 노드(트리의 요소)를 만들때마다 인스턴스를 만들어주고 리스트에 넣었다.
리스트에 입력받은 부모 노드가 존재하면 자식으로 붙여줌
이걸 반복해서 트리는 만들었는데 가중치가 가장 크고 멀리 있는 두 값을 찾는게 문제였음..
totalvalue라는 노드 1부터 각 노드들까지 도달하는 value들의 합을 저장하는 변수를 만들고
리스트를 내림차순으로 정렬함.
가장 먼저 있는 노드 두개의 부모노드를 찾아 올라가서 서로 같은 노드일때 더하기만 하면 될 줄 알았는데 틀렸다고 나왔다.
반례가 있었다
이진 트리가 아닐 때
5
1 2 33
2 3 34
1 4 22
1 5 10
----------------
일자 트리일 때
5
1 2 10
2 3 10
3 4 10
4 5 10
값이 89가 나와야 맞는 거 같은데 100이 나옴
탐색하는 걸 더 찾아봐야겠다..
|
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
|
using System;
using System.Collections.Generic;
using System.ComponentModel.Design;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;
namespace _1967
{
public class Node
{
public int num;
public int value;
public int totalValue;
public int depth;
public List<Node> cNodeList;
public Node pNode;
}
class Program
{
static int result1;
static int result2;
static int result3;
static void Main(string[] args)
{
Program p = new Program();
Node head = new Node();
head.num = 1;
head.depth = 1;
head.pNode = null;
head.cNodeList = new List<Node>();
List<Node> list = new List<Node>();
list.Add(head);
int length = Int32.Parse(Console.ReadLine());
if (length > 0 && length <= 10000)
{
for (int i = 2; i <= length; i++)
{
string[] strInput = Console.ReadLine().Split(' ');
int pNodeNum = Int32.Parse(strInput[0]);
int cNodeNum = Int32.Parse(strInput[1]);
int value = Int32.Parse(strInput[2]);
if (value <= 100 && value > 0)
{
Node newNode = p.CreateNode(cNodeNum, value);
list.Add(newNode);
p.AppendNode(pNodeNum, newNode, list);
}
}
}
var newList = list.OrderByDescending(x => x.totalValue).ToList();
for(int i=1; i<newList.Count; i++)
{
p.FindResult(newList[0], newList[i]); //그 다음 깊은거 하나씩
}
}
public Node CreateNode(int cNodeNum, int value)
{
Node node = new Node();
node.num = cNodeNum;
node.value = value;
node.totalValue = node.value;
node.cNodeList = new List<Node>();
return node;
}
public void AppendNode(int pNodeNum, Node newNode, List<Node> list)
{
if (list.Exists(x => x.num == pNodeNum))
{
Node pNode = list.Find(x => x.num == pNodeNum);
pNode.cNodeList.Add(newNode);
newNode.pNode = pNode;
newNode.depth = pNode.depth + 1;
newNode.totalValue = newNode.value + pNode.totalValue;
}
}
public void FindResult(Node x, Node y)
{
if(x.depth==y.depth)
{
if(x==y)
{
//끝내고 반환
int result = result1 + result2;
if(result3==0 || result3>result)
{
result3 = result;
Console.WriteLine(result3);
return;
}
}
else
{
result1 += x.value;
result2 += y.value;
FindResult(x.pNode, y.pNode);
}
}
else
{
if(x.num!=1 && y.num!=1)
{
result1 += x.value;
result2 += y.value;
FindResult(x.pNode, y.pNode);
}
else if(x.num==1)
{
result2 += y.value;
FindResult(x, y.pNode);
}
else if (y.num == 1)
{
result1 += x.value;
FindResult(x.pNode, y);
}
else if(x.pNode ==y)
{
result1 = x.totalValue;
return;
}
}
}
}
}
|
주어진 예제는 잘 나옴
답이 89인듯
40이 나와야함
'C# > 알고리즘' 카테고리의 다른 글
| 15. 8980번 택배 (0) | 2020.09.05 |
|---|---|
| 14. 4963번 섬의 개수 (0) | 2020.09.05 |
| 12. 1074번 Z (시간 줄임) (0) | 2020.07.11 |
| 11. 2504번 괄호의 값 (해결) (0) | 2020.06.22 |
| 10. 10845번 큐 (해결) (0) | 2020.06.21 |