310 Minimum Height Trees

• 310 Minimum Height Trees
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각
      • 1 코드
      • 1 결과: 실패
    • 2nd 책
      • 2 설명
      • 2 코드
      • 2 결과: 성공
      • 2 Greedy 풀이와의 속도 비교

310 Minimum Height Trees

문제

A tree is an undirected graph in which any two vertices are connected by exactly one path.
In other words, any connected graph without simple cycles is a tree.

• 트리는 방향 없는 그래프로, 두 정점(verticles)이 하나의 길로 연결

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root.

• 0과 n-1로 표시된 n개의 노드로 구성된 트리가 주어졌을 때,
• n-1개의 edges에서 edges[i] = [ai, bi]는 두 노드 ai와 bi 사이에 무방향 간선이 있음을 의미하고, 어떤 노드든 트리의 루트로 선택할 수 있다

When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

• 노드 x를 루트로 선택할 때, 그 트리는 높이 h를 갖는다
• 모든 가능한 트리 누트에서, 가장 작은 높이 min(h)를 minimum height trees(MHTs)라 한다

Return a list of all MHTs’ root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

조건

• 1 <= n <= 2 * 10^4
  • 최대 노드 20,000개
• edges.length == n - 1
• 0 <= ai, bi < n
• ai != bi
• All the pairs (ai, bi) are distinct.
• The given input is guaranteed to be a tree and there will be no repeated edges.

예제

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: 
    As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Input: n = 1, edges = []
Output: [0]

Input: n = 2, edges = [[0,1]]
Output: [0,1]

해결

1st

1 생각

• 루트가 가능한 노드 목록이 필요할 거 같다
• 가능한 모든 루트를 찾아야 하므로 모든 노드를 순회해야 할 거 같다
  • 근데 노드가 최대 20000개인데, 분명 시간 초과 날 거 같은데?
  • 그래도 뭐, 일단 해보자.

1 코드

def first(self, n: int, edges: List[List[int]]) -> List[int]:
    # Wrong Answer
    if n == 1:
        return [0]

    adjacent_list = collections.defaultdict(list)

    for edge in edges:
        adjacent_list[edge[0]].append(edge)
        adjacent_list[edge[1]].append([edge[1], edge[0]])

    possbile_roots = [*adjacent_list]
    """ print(adjacent_list)
    print(possbile_roots) """

    def dfs(root, neighbor, path, depth):
        if root == neighbor:
            return depth - 1

        depth_max = depth  
        # print('root:', root, ', neighbor:', neighbor, ', path:', path)
        for node in adjacent_list[neighbor]:
            if node[1] not in path:
                depth_new = dfs(root, node[1], path + [node[1]], depth + 1)
                depth_max = max(depth_max, depth_new)
                # print('depth_new:', depth_new, ', depth_max:', depth_max)
        
        return depth_max

    depth_dict = collections.defaultdict(list)
    depth_min = 20001
    while possbile_roots:
        depth_max = 0
        root = possbile_roots.pop(0)

        for node in adjacent_list[root]:
            depth_max = max(depth_max, dfs(root, node[1], [node[1]], 1))
        
        if root not in depth_dict[depth_max]:
            depth_min = min(depth_max, depth_min)
        depth_dict[depth_max].append(root)

    """ print(depth_min)
    print(depth_dict) """

    return depth_dict[depth_min]

1 결과: 실패

• 역시 시간 초과가 떴다

'''
n = 1515
time_limit_case = [
    [0,1],[1,2],[2,3],[0,4],[3,5],[0,6],[1,7],[0,8],[1,9],[0,10],[7,11],[5,12],[12,13],[4,14],[10,15],[15,16],
    [0,17],[13,18],[10,19],[10,20],[11,21],[1,22],[12,23],[9,24],[9,25],[19,26],[5,27],[3,28],[2,29],[2,30],
    [17,31],[24,32],[22,33],[14,34],[19,35],[4,36],[33,37],[20,38],[9,39],[31,40],[36,41],[25,42],[12,43],[30,44],
    [40,45],[11,46],[1,47],[20,48],[11,49],[42,50],[26,51],[5,52],[26,53],[23,54],[39,55],[8,56],[46,57],[55,58],
    [57,59],[58,60],[24,61],[59,62],[47,63],[45,64],[0,65],[6,66],[43,67],[1,68],[0,69],[41,70],[69,71],[19,72],
    [45,73],[58,74],[28,75],[59,76],[49,77],[40,78],[7,79],[13,80],[60,81],[4,82],[61,83],[24,84],[39,85],[51,86],
    [2,87],[20,88],[3,89],[22,90],[89,91],[82,92],[66,93],[29,94],[74,95],[87,96],[57,97],[67,98],[53,99],[99,100],
    [42,101],[45,102],[10,103],[15,104],[6,105],[83,106],[86,107],[83,108],[78,109],[83,110],[25,111],[101,112],
    [105,113],[87,114],[105,115],[79,116],[51,117],[41,118],[5,119],[96,120],[11,121],[42,122],[21,123],[78,124],
    [96,125],[83,126],[52,127],[73,128],[36,129],[43,130],[84,131],[104,132],[7,133],[123,134],[57,135],[28,136],
    [18,137],[39,138],[27,139],[105,140],[99,141],[103,142],[140,143],[82,144],[11,145],[49,146],[35,147],[66,148],
    [143,149],[107,150],[10,151],[81,152],[9,153],[85,154],[150,155],[60,156],[103,157],[29,158],[153,159],[72,160],
    [34,161],[63,162],[136,163],[131,164],[37,165],[86,166],[146,167],[81,168],[28,169],[166,170],[1,171],[23,172],
    [77,173],[1,174],[171,175],[37,176],[62,177],[38,178],[153,179],[177,180],[127,181],[8,182],[174,183],[50,184],
    [31,185],[69,186],[58,187],[39,188],[178,189],[76,190],[61,191],[101,192],[82,193],[141,194],[134,195],[179,196],
    [183,197],[140,198],[180,199],[88,200],[161,201],[0,202],[83,203],[180,204],[54,205],[145,206],[200,207],[20,208],
    [193,209],[111,210],[35,211],[92,212],[190,213],[115,214],[4,215],[127,216],[132,217],[110,218],[154,219],[39,220],
    [10,221],[55,222],[13,223],[31,224],[45,225],[209,226],[104,227],[62,228],[74,229],[96,230],[115,231],[93,232],
    [90,233],[46,234],[213,235],[132,236],[16,237],[215,238],[74,239],[67,240],[96,241],[151,242],[98,243],[40,244],
    [240,245],[176,246],[61,247],[126,248],[237,249],[100,250],[107,251],[211,252],[234,253],[208,254],[170,255],
    [251,256],[30,257],[88,258],[257,259],[254,260],[147,261],[97,262],[169,263],[29,264],[199,265],[8,266],[18,267],
    [46,268],[204,269],[252,270],[136,271],[197,272],[208,273],[94,274],[131,275],[271,276],[70,277],[233,278],[95,279],
    [224,280],[133,281],[173,282],[256,283],[129,284],[271,285],[29,286],[269,287],[29,288],[1,289],[51,290],[273,291],
    [45,292],[89,293],[115,294],[87,295],[4,296],[102,297],[3,298],[104,299],[276,300],[207,301],[141,302],[82,303],
    [47,304],[267,305],[49,306],[187,307],[254,308],[103,309],[105,310],[306,311],[20,312],[284,313],[227,314],
    [195,315],[4,316],[102,317],[173,318],[206,319],[40,320],[44,321],[258,322],[33,323],[166,324],[54,325],[166,326],
    [184,327],[181,328],[12,329],[199,330],[211,331],[305,332],[117,333],[223,334],[249,335],[36,336],[184,337],
    [106,338],[174,339],[241,340],[27,341],[279,342],[322,343],[11,344],[44,345],[206,346],[214,347],[68,348],[74,349],
    [263,350],[49,351],[224,352],[135,353],[337,354],[218,355],[193,356],[273,357],[305,358],[267,359],[52,360],
    [130,361],[94,362],[327,363],[233,364],[0,365],[332,366],[95,367],[217,368],[279,369],[3,370],[227,371],[165,372],
    [372,373],[112,374],[371,375],[132,376],[21,377],[158,378],[322,379],[41,380],[104,381],[119,382],[125,383],
    [43,384],[62,385],[101,386],[324,387],[349,388],[123,389],[173,390],[384,391],[294,392],[296,393],[159,394],
    [225,395],[4,396],[294,397],[236,398],[183,399],[305,400],[144,401],[83,402],[277,403],[68,404],[154,405],[374,406],
    [165,407],[193,408],[302,409],[231,410],[58,411],[267,412],[65,413],[378,414],[380,415],[362,416],[35,417],
    [124,418],[20,419],[364,420],[30,421],[4,422],[141,423],[215,424],[120,425],[39,426],[100,427],[250,428],
    [169,429],[378,430],[218,431],[1,432],[134,433],[60,434],[409,435],[275,436],[422,437],[415,438],[391,439],
    [334,440],[146,441],[156,442],[117,443],[230,444],[371,445],[170,446],[237,447],[3,448],[34,449],[392,450],
    [303,451],[161,452],[142,453],[322,454],[130,455],[186,456],[308,457],[24,458],[456,459],[11,460],[333,461],
    [459,462],[295,463],[205,464],[362,465],[13,466],[408,467],[299,468],[452,469],[346,470],[129,471],[136,472],
    [357,473],[277,474],[327,475],[338,476],[407,477],[42,478],[43,479],[282,480],[1,481],[238,482],[408,483],
    [100,484],[383,485],[158,486],[321,487],[204,488],[323,489],[284,490],[95,491],[379,492],[63,493],[159,494],
    [131,495],[56,496],[284,497],[39,498],[45,499],[202,500],[258,501],[242,502],[190,503],[394,504],[260,505],
    [443,506],[451,507],[399,508],[35,509],[15,510],[434,511],[194,512],[4,513],[157,514],[171,515],[421,516],
    [146,517],[517,518],[357,519],[32,520],[438,521],[92,522],[66,523],[14,524],[180,525],[450,526],[502,527],
    [374,528],[475,529],[242,530],[150,531],[85,532],[259,533],[315,534],[433,535],[393,536],[491,537],[364,538],
    [233,539],[229,540],[356,541],[371,542],[446,543],[464,544],[232,545],[521,546],[241,547],[324,548],[429,549],
    [173,550],[382,551],[19,552],[158,553],[496,554],[534,555],[316,556],[514,557],[348,558],[314,559],[364,560],
    [506,561],[436,562],[496,563],[237,564],[255,565],[411,566],[486,567],[257,568],[396,569],[264,570],[444,571],
    [192,572],[442,573],[468,574],[441,575],[503,576],[420,577],[436,578],[52,579],[1,580],[248,581],[43,582],
    [582,583],[0,584],[567,585],[527,586],[99,587],[261,588],[324,589],[107,590],[213,591],[174,592],[451,593],
    [17,594],[478,595],[104,596],[498,597],[569,598],[503,599],[37,600],[285,601],[76,602],[413,603],[492,604],
    [343,605],[253,606],[264,607],[556,608],[322,609],[368,610],[163,611],[280,612],[170,613],[100,614],[95,615],
    [156,616],[59,617],[235,618],[64,619],[333,620],[179,621],[159,622],[543,623],[575,624],[546,625],[192,626],
    [526,627],[492,628],[195,629],[202,630],[484,631],[105,632],[274,633],[492,634],[289,635],[129,636],[38,637],
    [637,638],[422,639],[338,640],[265,641],[314,642],[486,643],[1,644],[378,645],[492,646],[639,647],[354,648],
    [106,649],[198,650],[134,651],[429,652],[411,653],[155,654],[585,655],[227,656],[311,657],[185,658],[60,659],
    [444,660],[633,661],[461,662],[619,663],[267,664],[365,665],[101,666],[342,667],[436,668],[656,669],[28,670],
    [607,671],[270,672],[598,673],[383,674],[73,675],[544,676],[661,677],[490,678],[403,679],[591,680],[678,681],
    [457,682],[97,683],[511,684],[643,685],[66,686],[526,687],[191,688],[64,689],[10,690],[570,691],[139,692],
    [100,693],[598,694],[591,695],[340,696],[627,697],[91,698],[499,699],[231,700],[57,701],[193,702],[349,703],
    [68,704],[491,705],[673,706],[269,707],[565,708],[155,709],[126,710],[268,711],[270,712],[100,713],[43,714],
    [263,715],[96,716],[45,717],[82,718],[309,719],[663,720],[347,721],[201,722],[28,723],[459,724],[688,725],
    [397,726],[492,727],[522,728],[330,729],[728,730],[135,731],[411,732],[719,733],[554,734],[484,735],[247,736],
    [75,737],[109,738],[181,739],[64,740],[92,741],[518,742],[21,743],[404,744],[490,745],[658,746],[654,747],
    [632,748],[414,749],[345,750],[492,751],[78,752],[20,753],[596,754],[214,755],[174,756],[161,757],[289,758],
    [52,759],[241,760],[476,761],[3,762],[594,763],[56,764],[171,765],[92,766],[359,767],[683,768],[113,769],
    [235,770],[427,771],[182,772],[419,773],[740,774],[107,775],[157,776],[655,777],[396,778],[216,779],[52,780],
    [683,781],[97,782],[491,783],[121,784],[683,785],[359,786],[6,787],[778,788],[343,789],[223,790],[480,791],
    [12,792],[710,793],[349,794],[127,795],[439,796],[677,797],[646,798],[61,799],[197,800],[61,801],[623,802],
    [521,803],[209,804],[284,805],[0,806],[485,807],[796,808],[625,809],[500,810],[150,811],[454,812],[62,813],
    [500,814],[346,815],[683,816],[441,817],[121,818],[196,819],[134,820],[682,821],[479,822],[678,823],[320,824],
    [744,825],[698,826],[82,827],[722,828],[309,829],[250,830],[481,831],[232,832],[155,833],[798,834],[152,835],
    [186,836],[573,837],[138,838],[673,839],[197,840],[42,841],[62,842],[5,843],[63,844],[30,845],[382,846],[610,847],
    [265,848],[309,849],[498,850],[844,851],[306,852],[91,853],[663,854],[239,855],[680,856],[469,857],[706,858],
    [190,859],[390,860],[62,861],[375,862],[350,863],[314,864],[198,865],[352,866],[719,867],[197,868],[270,869],
    [77,870],[561,871],[477,872],[309,873],[246,874],[267,875],[36,876],[702,877],[664,878],[416,879],[406,880],
    [693,881],[212,882],[696,883],[229,884],[12,885],[481,886],[504,887],[369,888],[379,889],[572,890],[384,891],
    [388,892],[667,893],[235,894],[575,895],[92,896],[801,897],[544,898],[218,899],[707,900],[132,901],[762,902],
    [754,903],[728,904],[576,905],[167,906],[654,907],[695,908],[212,909],[898,910],[857,911],[7,912],[816,913],
    [712,914],[48,915],[765,916],[516,917],[555,918],[208,919],[702,920],[225,921],[518,922],[530,923],[646,924],
    [324,925],[668,926],[896,927],[724,928],[204,929],[514,930],[538,931],[622,932],[591,933],[100,934],[134,935],
    [721,936],[564,937],[226,938],[419,939],[782,940],[621,941],[547,942],[794,943],[896,944],[654,945],[42,946],
    [165,947],[817,948],[480,949],[621,950],[518,951],[508,952],[854,953],[461,954],[557,955],[138,956],[432,957],
    [548,958],[149,959],[230,960],[813,961],[338,962],[694,963],[283,964],[349,965],[729,966],[495,967],[453,968],
    [704,969],[437,970],[17,971],[279,972],[204,973],[206,974],[377,975],[964,976],[615,977],[572,978],[937,979],
    [733,980],[137,981],[54,982],[516,983],[119,984],[542,985],[250,986],[938,987],[682,988],[64,989],[29,990],
    [291,991],[501,992],[178,993],[415,994],[845,995],[7,996],[667,997],[205,998],[689,999],[583,1000],[755,1001],
    [382,1002],[741,1003],[168,1004],[991,1005],[433,1006],[6,1007],[151,1008],[286,1009],[678,1010],[976,1011],
    [21,1012],[555,1013],[331,1014],[190,1015],[66,1016],[67,1017],[798,1018],[451,1019],[172,1020],[731,1021],
    [855,1022],[831,1023],[883,1024],[68,1025],[391,1026],[867,1027],[464,1028],[185,1029],[962,1030],[651,1031],
    [292,1032],[467,1033],[378,1034],[327,1035],[895,1036],[315,1037],[717,1038],[64,1039],[830,1040],[149,1041],
    [420,1042],[517,1043],[805,1044],[377,1045],[628,1046],[209,1047],[945,1048],[753,1049],[154,1050],[382,1051],
    [158,1052],[543,1053],[689,1054],[637,1055],[828,1056],[361,1057],[413,1058],[618,1059],[248,1060],[342,1061],
    [57,1062],[175,1063],[943,1064],[802,1065],[267,1066],[735,1067],[1018,1068],[348,1069],[683,1070],[387,1071],
    [812,1072],[845,1073],[0,1074],[710,1075],[41,1076],[157,1077],[731,1078],[562,1079],[1073,1080],[80,1081],
    [939,1082],[223,1083],[146,1084],[1001,1085],[726,1086],[646,1087],[892,1088],[541,1089],[736,1090],[511,1091],
    [1069,1092],[742,1093],[883,1094],[852,1095],[165,1096],[3,1097],[873,1098],[831,1099],[259,1100],[1036,1101],
    [891,1102],[674,1103],[870,1104],[700,1105],[903,1106],[769,1107],[649,1108],[546,1109],[1058,1110],[897,1111],
    [94,1112],[924,1113],[606,1114],[340,1115],[967,1116],[403,1117],[988,1118],[736,1119],[873,1120],[708,1121],
    [412,1122],[1027,1123],[593,1124],[49,1125],[873,1126],[767,1127],[1049,1128],[908,1129],[126,1130],[886,1131],[684,1132],[230,1133],[361,1134],[784,1135],[288,1136],[1125,1137],[329,1138],[821,1139],[781,1140],[704,1141],[109,1142],[304,1143],[123,1144],[672,1145],[162,1146],[1140,1147],[204,1148],[591,1149],[845,1150],[504,1151],[840,1152],[689,1153],[129,1154],[329,1155],[574,1156],[934,1157],[869,1158],[1060,1159],[424,1160],[854,1161],[6,1162],[404,1163],[84,1164],[252,1165],[862,1166],[1092,1167],[749,1168],[257,1169],[410,1170],[872,1171],[1,1172],[570,1173],[650,1174],[345,1175],[108,1176],[900,1177],[328,1178],[703,1179],[539,1180],[136,1181],[411,1182],[344,1183],[28,1184],[961,1185],[835,1186],[571,1187],[546,1188],[945,1189],[553,1190],[774,1191],[477,1192],[646,1193],[958,1194],[1166,1195],[1167,1196],[981,1197],[85,1198],[230,1199],[402,1200],[685,1201],[467,1202],[480,1203],[65,1204],[334,1205],[1070,1206],[147,1207],[343,1208],[929,1209],[1056,1210],[830,1211],[459,1212],[316,1213],[692,1214],[930,1215],[746,1216],[1049,1217],[771,1218],[114,1219],[39,1220],[206,1221],[515,1222],[285,1223],[1205,1224],[733,1225],[697,1226],[155,1227],[1156,1228],[847,1229],[538,1230],[24,1231],[386,1232],[527,1233],[508,1234],[1069,1235],[885,1236],[944,1237],[408,1238],[354,1239],[997,1240],[9,1241],[495,1242],[694,1243],[728,1244],[922,1245],[1094,1246],[445,1247],[86,1248],[285,1249],[788,1250],[1099,1251],[923,1252],[980,1253],[1179,1254],[416,1255],[1196,1256],[1247,1257],[1246,1258],[883,1259],[1061,1260],[65,1261],[759,1262],[790,1263],[242,1264],[928,1265],[565,1266],[1199,1267],[233,1268],[857,1269],[382,1270],[598,1271],[388,1272],[390,1273],[541,1274],[179,1275],[353,1276],[622,1277],[658,1278],[1107,1279],[387,1280],[1039,1281],[494,1282],[1281,1283],[849,1284],[48,1285],[1161,1286],[856,1287],[524,1288],[915,1289],[150,1290],[532,1291],[525,1292],[668,1293],[959,1294],[450,1295],[421,1296],[948,1297],[299,1298],[661,1299],[873,1300],[1038,1301],[1056,1302],[1202,1303],[480,1304],[946,1305],[380,1306],[406,1307],[964,1308],[780,1309],[1016,1310],[448,1311],[309,1312],[157,1313],[109,1314],[531,1315],[1264,1316],[1072,1317],[104,1318],[675,1319],[740,1320],[413,1321],[483,1322],[924,1323],[64,1324],[1093,1325],[1089,1326],[172,1327],[1200,1328],[491,1329],[1055,1330],[552,1331],[470,1332],[358,1333],[291,1334],[256,1335],[388,1336],[511,1337],[287,1338],[126,1339],[180,1340],[16,1341],[1143,1342],[1191,1343],[1201,1344],[660,1345],[476,1346],[909,1347],[1298,1348],[103,1349],[1164,1350],[460,1351],[1334,1352],[349,1353],[283,1354],[1200,1355],[1194,1356],[1218,1357],[73,1358],[937,1359],[1078,1360],[121,1361],[5,1362],[1139,1363],[582,1364],[1056,1365],[1102,1366],[403,1367],[181,1368],[674,1369],[945,1370],[21,1371],[1285,1372],[433,1373],[1196,1374],[1320,1375],[1115,1376],[52,1377],[1007,1378],[474,1379],[810,1380],[443,1381],[456,1382],[651,1383],[183,1384],[1295,1385],[657,1386],[1009,1387],[1322,1388],[476,1389],[400,1390],[315,1391],[908,1392],[720,1393],[567,1394],[408,1395],[674,1396],[614,1397],[904,1398],[926,1399],[911,1400],[621,1401],[330,1402],[734,1403],[947,1404],[649,1405],[793,1406],[1034,1407],[150,1408],[707,1409],[674,1410],[544,1411],[1304,1412],[653,1413],[683,1414],[845,1415],[986,1416],[787,1417],[677,1418],[226,1419],[810,1420],[1138,1421],[937,1422],[999,1423],[325,1424],[1348,1425],[362,1426],[1083,1427],[91,1428],[1024,1429],[1093,1430],[1322,1431],[356,1432],[240,1433],[296,1434],[1090,1435],[1018,1436],[368,1437],[877,1438],[783,1439],[1030,1440],[1060,1441],[119,1442],[423,1443],[256,1444],[1033,1445],[367,1446],[1153,1447],[275,1448],[834,1449],[769,1450],[870,1451],[253,1452],[1354,1453],[770,1454],[659,1455],[214,1456],[781,1457],[1353,1458],[245,1459],[675,1460],[1025,1461],[509,1462],[1302,1463],[475,1464],[1213,1465],[898,1466],[791,1467],[966,1468],[739,1469],[601,1470],[1119,1471],[976,1472],[1095,1473],[64,1474],[1395,1475],[1225,1476],[1447,1477],[679,1478],[577,1479],[799,1480],[460,1481],[1352,1482],[1137,1483],[719,1484],[1294,1485],[91,1486],[995,1487],[466,1488],[631,1489],[508,1490],[1235,1491],[1183,1492],[482,1493],[813,1494],[443,1495],[398,1496],[61,1497],[218,1498],[253,1499],[279,1500],[738,1501],[477,1502],[1182,1503],[376,1504],[1051,1505],[48,1506],[485,1507],[1061,1508],[1032,1509],[398,1510],[220,1511],[1394,1512],[974,1513],[968,1514]]
'''

2nd 책

2 설명

• 최소 높이 구성하려면? 가장 가운데 있는 값이 루트여야 한다
  • 리프 노드를 하나씩 제거해 나가면서 남아 있는 값을 찾으면, 이 값이 가장 가운데에 있는 값
  • 루트마다 모두 순회하며 가장 큰 값을 찾는 게 아니라, 끝에서부터 삭제하며 올라간다
• 지워 나간다는 사고 방식은 p.311 섬의 개수 문제와 유사하다

'''
[
    [1,3], 
    [2,3],
    [3,4],
    [3,5],
    [4,6],
    [6,10],
    [5,7],
    [5,8],
    [8,9],
]
'''
(1.x)9
     |
(2.x)8    1(1.x)
     |    |
(3.x)5----3----2(1.x)
     |    |
(1.x)7    4(3.x)
          |
     (2-x)6----10(1.x)
          

• 리프 노드 제거 순서
  • (1.x): 1, 2, 7, 9, 10
  • (2.x): 6, 8
  • (3.x): 4, 5

2 코드

def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
    graph = collections.defaultdict(list)
    for node_from, node_to in edges:
        # undirected로 양방향 가능
        graph[node_from].append(node_to)
        graph[node_to].append(node_from)

    # 리프 노드를 담는다
    leaves = []
    for i in range(n + 1):
        # 리프 노드는 연결된 노드가 하나밖에 없다
        if len(graph[i]) == 1:
            leaves.append(i)
    # 루트가 남을 때까지 반복
    while n > 2: # 왜 2인가? 하나만 남거나, 서로 연결된 두 노드만 남거나 둘 중 하나
        '''
        n은 존재하는 노드의 수. 연결된 노드의 개수를 지워나가다 보면 루트 노드 개수만 남게 되는데, 루트 노드가 1개 또는 2개 존재 가능하다
        [[8,7],[7,6],[6,5],[6,4],[6,3],[3,2],[3,1],[1,0]]
        3개 이상은 불가능할까? 3개가 되면 6, 3, 1 남고, 6과 1이 제거되면서 3만 루트 노드가 된다
        8   5   2
        |   |   |
        7---6---3---1---0
            |
            4
        
        이 경우에는 6, 3 두 개만 남게 되고, 그러면 6과 3 어디서 출발하든 최대 높이는 같게 된다
        8   5   2   ?
        |   |   |   |
        7---6---3---1---0
            |
            4
        '''
        n -= len(leaves)
        leaves_new = []
        # 리프 노드와 연결된 노드를 서로 지운다(지워 나간다는 사고 방식은 p.311 섬의 개수 문제와 유사하다)
        for leaf in leaves:
            # print('leaf: ', leaf, ', graph: ', graph)
            # 리프노드와 연결된 neigbor를 꺼내서
            neighbor = graph[leaf].pop()
            # 리프 노드를 제거한다
            graph[neighbor].remove(leaf)
            # print('neighbor: ', neighbor, ', graph: ', graph)

            # 연결된 노드가 하나만 있는 새로운 리프 노드가 있다면, 계속 지워나가도록 leaves를 바꾼다
            if len(graph[neighbor]) == 1:
                leaves_new.append(neighbor)

        leaves = leaves_new
        # print()
    
    return leaves

2 결과: 성공

Runtime: 236 ms, faster than 69.10% of Python3 online submissions for Minimum Height Trees.
Memory Usage: 18.2 MB, less than 93.93% of Python3 online submissions for Minimum Height Trees.

2 Greedy 풀이와의 속도 비교

sol_by_book = 0
sol_by_me = 0
for i in range(10):
    t0 = time.time()
    print(s.findMinHeightTrees(1515, case_time_limit))
    t1 = time.time()
    sol_by_book += t1 - t0
    t0 = time.time()
    print(s.first(1515, case_time_limit))
    t1 = time.time()
    sol_by_me += t1 - t0

print(sol_by_book / 10)
print(sol_by_me / 10)
'''
0.0025956153869628905
2.083551549911499
'''

• 10번 실행 시 평균 800배… 차이가 난다!