{"id":26950,"date":"2024-10-27T11:53:59","date_gmt":"2024-10-27T11:53:59","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26950"},"modified":"2024-11-26T07:25:24","modified_gmt":"2024-11-26T07:25:24","slug":"%ec%9e%90%eb%b0%94-%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\/26950\/","title":{"rendered":"\uc790\ubc14 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ud2b8\ub9ac\uc758 \uc9c0\ub984 \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

\n
\n

1. \ubb38\uc81c \uc815\uc758<\/h2>\n

\n \uc8fc\uc5b4\uc9c4 \ud2b8\ub9ac\uc5d0\uc11c \uc9c0\ub984\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\ub294 \uc54c\uace0\ub9ac\uc998\uc801\uc778 \uc0ac\uace0\ub97c \uc694\uad6c\ud558\ub294 \uc911\uc694\ud55c \uc8fc\uc81c\uc785\ub2c8\ub2e4.
\n \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc740 \ub450 \uac1c\uc758 \uc815\uc810 \uac04\uc758 \ucd5c\uc7a5 \uacbd\ub85c\uc758 \uae38\uc774\ub97c \ub9d0\ud569\ub2c8\ub2e4. \uc774\ub294 \ud2b8\ub9ac \uad6c\uc870\uc758 \ud2b9\uc131\uc744 \ud65c\uc6a9\ud558\uc5ec \uad6c\ud560 \uc218 \uc788\uc73c\uba70, \uc5ec\ub7ec \uac00\uc9c0 \uc751\uc6a9 \ubb38\uc81c\uc758 \uae30\ucd08\uac00 \ub429\ub2c8\ub2e4.
\n \uadf8\ub7ec\ubbc0\ub85c \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uac83\uc740 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uad1c\ucc2e\uc740 \uc131\uc801\uc744 \uc5bb\uae30 \uc704\ud55c \uc911\uc694\ud55c \ub2e8\uacc4\uc785\ub2c8\ub2e4.\n <\/p>\n<\/section>\n

\n

2. \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h2>\n

\n \ud2b8\ub9ac\ub294 \ub178\ub4dc\ub85c \uad6c\uc131\ub41c \ube44\uc120\ud615 \uc790\ub8cc\uad6c\uc870\ub85c\uc11c, \ub808\ubca8\uacfc \ubd80\ubaa8-\uc790\uc2dd \uad00\uacc4\uac00 \uc874\uc7ac\ud569\ub2c8\ub2e4. \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc744 \uad6c\ud558\uae30 \uc704\ud574\uc11c\ub294 \ud2b8\ub9ac\ub97c \uadf8\ub798\ud504\uc758 \uc77c\uc885\uc73c\ub85c \uc0dd\uac01\ud558\uace0
\n \uadf8\ub798\ud504 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4.
\n \uc9c0\ub984\uc744 \uad6c\ud558\ub294 \uac00\uc7a5 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc740 \ub450 \ubc88\uc758 \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n

\n \uccab \ubc88\uc9f8 DFS\ub294 \uc784\uc758\uc758 \ub178\ub4dc\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \uac00\uc7a5 \uba3c \ub178\ub4dc\ub97c \ucc3e\uc2b5\ub2c8\ub2e4. \uadf8 \ub2e4\uc74c, \uc774 \uc0c8\ub85c \ucc3e\uc740 \ub178\ub4dc\uc5d0\uc11c \ub2e4\uc2dc DFS\ub97c \uc2e4\ud589\ud558\uc5ec \ucd5c\ub300 \uac70\ub9ac\ub97c \uce21\uc815\ud558\uba74
\n \uadf8\uac83\uc774 \ud2b8\ub9ac\uc758 \uc9c0\ub984\uc774 \ub429\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ubc29\uc2dd\uc740 O(N)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uba70, \uc774\ub294 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc778 \ud574\uacb0\ucc45\uc785\ub2c8\ub2e4.\n <\/p>\n<\/section>\n

\n

3. \ubb38\uc81c \ud574\uacb0 \uc804\ub7b5<\/h2>\n

\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uc804\ub7b5\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.\n <\/p>\n

    \n
  1. \n\ud2b8\ub9ac \uad6c\uc131:<\/strong> \uba3c\uc800 \uc8fc\uc5b4\uc9c4 \ub370\uc774\ud130\ub97c \ubc14\ud0d5\uc73c\ub85c \ud2b8\ub9ac \uad6c\uc870\ub97c \ub9cc\ub4ed\ub2c8\ub2e4.\n <\/li>\n
  2. \nDFS \uad6c\ud604:<\/strong> \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud558\uc5ec \ud2b9\uc815 \ub178\ub4dc\uc5d0\uc11c \uac00\uc7a5 \uba3c \ub178\ub4dc\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.\n <\/li>\n
  3. \n\uc9c0\ub984 \uacc4\uc0b0:<\/strong> \uccab \ubc88\uc9f8 DFS\uc5d0\uc11c \ucc3e\uc740 \uba3c \ub178\ub4dc\uc5d0\uc11c \ub2e4\uc2dc DFS\ub97c \uc2e4\ud589\ud558\uc5ec \uc9c0\ub984\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.\n <\/li>\n<\/ol>\n<\/section>\n
    \n

    4. \uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
    \n\nimport java.util.*;\n\nclass TreeNode {\n    int val;\n    List children;\n\n    TreeNode(int x) {\n        val = x;\n        children = new ArrayList<>();\n    }\n}\n\npublic class DiameterOfTree {\n\n    private int maxDiameter = 0;\n\n    public int getTreeDiameter(TreeNode root) {\n        if (root == null) return 0;\n        dfs(root);\n        return maxDiameter;\n    }\n\n    private int dfs(TreeNode node) {\n        if (node == null) return 0;\n\n        int firstMax = 0; \n        int secondMax = 0;\n\n        for (TreeNode child : node.children) {\n            int childDepth = dfs(child);\n            if (childDepth > firstMax) {\n                secondMax = firstMax;\n                firstMax = childDepth;\n            } else if (childDepth > secondMax) {\n                secondMax = childDepth;\n            }\n        }\n\n        maxDiameter = Math.max(maxDiameter, firstMax + secondMax);\n        return firstMax + 1;\n    }\n\n    public static void main(String[] args) {\n        TreeNode root = new TreeNode(1);\n        TreeNode node2 = new TreeNode(2);\n        TreeNode node3 = new TreeNode(3);\n        TreeNode node4 = new TreeNode(4);\n        TreeNode node5 = new TreeNode(5);\n\n        root.children.add(node2);\n        root.children.add(node3);\n        node2.children.add(node4);\n        node2.children.add(node5);\n\n        DiameterOfTree diameter = new DiameterOfTree();\n        int result = diameter.getTreeDiameter(root);\n        System.out.println(\"\ud2b8\ub9ac\uc758 \uc9c0\ub984: \" + result);\n    }\n}\n<\/treenode><\/code>\n            <\/pre>\n
    \n                \uc704\uc758 \ucf54\ub4dc\ub294 \uc6b0\uc120 TreeNode \ud074\ub798\uc2a4\ub97c \uc815\uc758\ud558\uace0, \uac01 \ub178\ub4dc\ub97c \uc5f0\uacb0\ud558\ub294 \ud2b8\ub9ac\ub97c \ub9cc\ub4ed\ub2c8\ub2e4.
    \n                main \uba54\uc18c\ub4dc\ub294 \ud2b8\ub9ac\ub97c \uc124\uc815\ud558\uace0 getTreeDiameter \uba54\uc18c\ub4dc\ub97c \ud1b5\ud558\uc5ec \uc9c0\ub984\uc744 \uacc4\uc0b0\ud558\ub3c4\ub85d \ub418\uc5b4 \uc788\uc2b5\ub2c8\ub2e4.\n            <\/p>\n<\/section>\n
    \n
    5. \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \n                \uc774 \ubd80\ubd84\uc5d0\uc11c\ub294 \ucf54\ub4dc\uc758 \uc8fc\uc694 \ubd80\ubd84\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n            <\/p>\n
    TreeNode \ud074\ub798\uc2a4<\/h3>\n
    \n                TreeNode \ud074\ub798\uc2a4\ub294 \ud2b8\ub9ac\uc758 \uac01 \ub178\ub4dc\ub97c \ub098\ud0c0\ub0b4\uba70, \ub178\ub4dc\uc758 \uac12\uacfc \uc790\uc2dd \ub178\ub4dc \ub9ac\uc2a4\ud2b8\ub97c \ud3ec\ud568\ud569\ub2c8\ub2e4.
    \n                \uc0dd\uc131\uc790\uc5d0\uc11c \uac12\uacfc \ube48 \uc790\uc2dd \ub9ac\uc2a4\ud2b8\ub97c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.\n            <\/p>\n
    diameter \ubcc0\uc218\ub97c \uc774\uc6a9\ud55c DFS<\/h3>\n
    \n                DFS\ub294 \uac01 \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud558\uba74\uc11c \uc790\uc2dd \ub178\ub4dc\ub4e4\uc758 \uae4a\uc774\ub97c \uad6c\ud558\uace0, \ucd5c\ub300 \uae4a\uc774\ub97c \uad6c\ud569\ub2c8\ub2e4.
    \n                \ub3d9\uc2dc\uc5d0 \ucd5c\ub300 \uc9c0\ub984\uc744 \uacc4\uc0b0\ud560 \ub54c, \ub450 \uac1c\uc758 \ucd5c\ub300 \uae4a\uc774\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4.
    \n                \uc774 \uae4a\uc774 \uac12\uc740 \ubd80\ubaa8 \ub178\ub4dc\ub85c \ub3cc\uc544\uac08 \ub54c 1\uc744 \ub354\ud574 \ubc18\ud658\ub429\ub2c8\ub2e4.\n            <\/p>\n<\/section>\n
    \n
    6. \uc131\ub2a5 \ubd84\uc11d<\/h2>\n
    \n                \uc704\uc758 \uad6c\ud604\uc740 O(N)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uba70, \uc5ec\uae30\uc11c N\uc740 \ub178\ub4dc\uc758 \uc218\uc785\ub2c8\ub2e4.
    \n                \uac01 \ub178\ub4dc\ub97c \ud55c \ubc88\uc529 \ubc29\ubb38\ud558\ubbc0\ub85c \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.
    \n                \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ub610\ud55c O(H)\ub85c, \uc5ec\uae30\uc11c H\ub294 \ud2b8\ub9ac\uc758 \ub192\uc774\uc5d0 \ud574\ub2f9\ud569\ub2c8\ub2e4.
    \n                \uc774\ub7ec\ud55c \uc131\ub2a5\uc740 \uc2e4\uc81c \ub300\uaddc\ubaa8 \ub370\uc774\ud130\uc5d0 \ub300\ud574\uc11c\ub3c4 \ub9e4\uc6b0 \uc88b\uc740 \uc131\ub2a5\uc744 \ubcf4\uc77c \uac83\uc785\ub2c8\ub2e4.\n            <\/p>\n<\/section>\n
    \n
    7. \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
    \n                \ub2e4\uc591\ud55c \ud2b8\ub9ac \uad6c\uc870\ub97c \uac16\ub294 \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub97c \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998\uc744 \uac80\uc99d\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
    \n                \uc608\ub97c \ub4e4\uc5b4, \ub2e4\uc74c\uacfc \uac19\uc740 \ud2b8\ub9ac \uad6c\uc870\ub97c \uace0\ub824\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n