{"id":27230,"date":"2024-10-27T13:44:45","date_gmt":"2024-10-27T13:44:45","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27230"},"modified":"2024-11-26T07:20:24","modified_gmt":"2024-11-26T07:20:24","slug":"%ed%8c%8c%ec%9d%b4%ec%8d%ac-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ed%8a%b8%eb%a6%ac%ec%9d%98-%ec%a7%80%eb%a6%84-%ea%b5%ac%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27230\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ud2b8\ub9ac\uc758 \uc9c0\ub984 \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

\n \ud2b8\ub9ac\ub294 \ucef4\ud4e8\ud130 \uacfc\ud559\uc5d0\uc11c \ub9e4\uc6b0 \uc911\uc694\ud55c \uc790\ub8cc\uad6c\uc870 \uc911 \ud558\ub098\uc785\ub2c8\ub2e4. \ud2b9\ud788 \ud2b8\ub9ac\ub294 \uacc4\uce35\uc801 \uad00\uacc4\ub97c \ub098\ud0c0\ub0b4\ub294 \ub370 \uc720\uc6a9\ud558\uba70, \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ub2e4\ub8f0 \uac83\uc785\ub2c8\ub2e4.
\n \uc9c0\ub984\uc774\ub780 \ud2b8\ub9ac\uc5d0\uc11c \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \uac00\uc7a5 \uae34 \uacbd\ub85c\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9) \ub610\ub294 BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\n \uc8fc\uc5b4\uc9c4 \ube44\uc5b4\uc788\uc9c0 \uc54a\uc740 \ud2b8\ub9ac\uc758 \uac01 \ub178\ub4dc\ub294 \uc815\uc218\ub85c \ud45c\uc2dc\ub429\ub2c8\ub2e4. \ud2b8\ub9ac\uc5d0\uc11c \ub450 \ub178\ub4dc \uc0ac\uc774\uc758 \uac00\uc7a5 \uae34 \uacbd\ub85c\uc758 \uae38\uc774\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uc138\uc694.
\n \uc785\ub825\uc73c\ub85c\ub294 \ud2b8\ub9ac\uc758 \ub178\ub4dc \uc218 N<\/code>\uacfc N-1<\/code>\uac1c\uc758 \uac04\uc120 \uc815\ubcf4\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \uac04\uc120 \uc815\ubcf4\ub294 \ub450 \ub178\ub4dc\ub97c \uc5f0\uacb0\ud558\ub294 \ud615\ud0dc\ub85c \uc81c\uacf5\ub429\ub2c8\ub2e4.
\n \uad6c\uccb4\uc801\uc73c\ub85c, \ub2e4\uc74c\uacfc \uac19\uc740 \ud615\uc2dd\uc758 \uc785\ub825\uc774 \uc8fc\uc5b4\uc9c8 \uac83\uc785\ub2c8\ub2e4:\n <\/p>\n

\n    N\n    a1 b1\n    a2 b2\n    ...\n    a(N-1) b(N-1)\n    <\/pre>\n
\n        \uc5ec\uae30\uc11c a<\/code>\uc640 b<\/code>\ub294 \uac01\uac01 \uc5f0\uacb0\ub41c \ub450 \ub178\ub4dc\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4.\n    <\/p>\n
\uc785\ub825 \uc608\uc2dc<\/h2>\n
\n    5\n    1 2\n    1 3\n    2 4\n    2 5\n    <\/pre>\n
\ucd9c\ub825 \uc608\uc2dc<\/h2>\n
\n    3\n    <\/pre>\n
\n        \uc774 \uacbd\uc6b0 \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc740 \ub178\ub4dc 4\uc640 \ub178\ub4dc 5 \uc0ac\uc774\ub85c, \uacbd\ub85c\ub294 4 \u2192 2 \u2192 1 \u2192 3 \ub610\ub294 4 \u2192 2 \u2192 5\ub85c \uad6c\uc131\ub429\ub2c8\ub2e4.
\n        \ub530\ub77c\uc11c \ucd9c\ub825\uc740 3<\/code>\uc785\ub2c8\ub2e4.\n    <\/p>\n
\ubb38\uc81c \ud480\uc774<\/h2>\n
\n        \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc744 \uad6c\ud558\uae30 \uc704\ud574\uc11c\ub294 DFS \ub610\ub294 BFS \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n        \uc77c\ubc18\uc801\uc778 \uc811\uadfc \ubc29\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.\n    <\/p>\n
    \n
  1. \n            \uccab \ubc88\uc9f8 \ub2e8\uacc4\ub85c, \uc784\uc758\uc758 \ub178\ub4dc\uc5d0\uc11c DFS\ub97c \uc2e4\ud589\ud574\uc11c \uac00\uc7a5 \uba3c \ub178\ub4dc\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.
    \n            \uc774 \ub178\ub4dc\ub97c X<\/code>\ub77c\uace0 \ud569\uc2dc\ub2e4.\n        <\/li>\n
  2. \n            \ub450 \ubc88\uc9f8 \ub2e8\uacc4\ub85c, \ub178\ub4dc X<\/code>\uc5d0\uc11c \ub2e4\uc2dc DFS\ub97c \uc2e4\ud589\ud558\uc5ec \uac00\uc7a5 \uba3c \ub178\ub4dc\uc778 Y<\/code>\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.
    \n            X<\/code>\uc640 Y<\/code> \uc0ac\uc774\uc758 \uacbd\ub85c\uac00 \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc774 \ub429\ub2c8\ub2e4.\n        <\/li>\n<\/ol>\n
    \n        \uc774 \uacfc\uc815\uc744 \ud1b5\ud574 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N)<\/code>\uc774 \ub418\uba70, \uc7ac\uadc0\uc801\uc73c\ub85c DFS\ub97c \ud638\ucd9c\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uad6c\ud604\ub429\ub2c8\ub2e4.\n    <\/p>\n
    \ud30c\uc774\uc36c \ucf54\ub4dc \uad6c\ud604<\/h2>\n
    \n        \uc774\uc81c \uc704\uc758 \ub85c\uc9c1\uc744 \ubc14\ud0d5\uc73c\ub85c \ud30c\uc774\uc36c\uc5d0\uc11c \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc744 \uad6c\ud558\ub294 \ucf54\ub4dc\ub97c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.
    \n        \uc544\ub7ab\ubd80\ubd84\uc5d0 \uc81c\uacf5\ud558\ub294 \ucf54\ub4dc\uc640 \ud568\uaed8 \uac01 \ub2e8\uacc4\uc758 \uc138\ubd80 \uacfc\uc815\uc744 \uc810\uac80\ud574 \ubcf4\uc138\uc694.\n    <\/p>\n
    \nfrom collections import defaultdict\n\ndef dfs(graph, node, visited):\n    visited.add(node)\n    max_distance = 0\n    farthest_node = node\n\n    for neighbor in graph[node]:\n        if neighbor not in visited:\n            distance, next_node = dfs(graph, neighbor, visited)\n            distance += 1\n            \n            if distance > max_distance:\n                max_distance = distance\n                farthest_node = next_node\n\n    return max_distance, farthest_node\n\ndef tree_diameter(edges, n):\n    graph = defaultdict(list)\n    \n    for a, b in edges:\n        graph[a].append(b)\n        graph[b].append(a)\n\n    # Step 1: start DFS from an arbitrary node (1)\n    visited = set()\n    _, farthest_node = dfs(graph, 1, visited)\n\n    # Step 2: start DFS from the farthest node found\n    visited.clear()\n    diameter, _ = dfs(graph, farthest_node, visited)\n\n    return diameter\n\n# Input reading part\nn = int(input())\nedges = [tuple(map(int, input().split())) for _ in range(n-1)]\nprint(tree_diameter(edges, n))\n<\/code>\n    <\/pre>\n
    \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \n        \uc704\uc758 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \uad6c\uc131\ub418\uc5b4 \uc788\uc2b5\ub2c8\ub2e4:\n    <\/p>\n