{"id":28403,"date":"2024-10-27T16:10:55","date_gmt":"2024-10-27T16:10:55","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28403"},"modified":"2024-11-26T07:03:07","modified_gmt":"2024-11-26T07:03:07","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b7%b8%eb%9e%98%ed%94%84%ec%9d%98-%ed%91%9c%ed%98%84","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28403\/","title":{"rendered":"\ucf54\ud2c0\ub9b0 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uadf8\ub798\ud504\uc758 \ud45c\ud604"},"content":{"rendered":"

<\/p>\n

\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \ucf54\ud2c0\ub9b0\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub098\uc624\ub294 \uadf8\ub798\ud504\uc758 \ud45c\ud604 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc790\uc138\ud788 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \uc5ec\ub7ec \ubd84\uc57c\uc5d0\uc11c \uaf64 \uc911\uc694\ud55c \uc790\ub8cc\uad6c\uc870\ub85c, \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \ub54c \ud544\uc218\uc801\uc778 \uadfc\ubcf8\uae30\ub2a5\uc744 \uac00\uc9c0\uace0 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \uadf8\ub798\ud504\ub97c \uc5b4\ub5bb\uac8c \ud45c\ud604\ud558\uace0, \uadf8 \ud45c\ud604\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n

\uadf8\ub798\ud504\ub780 \ubb34\uc5c7\uc778\uac00?<\/h2>\n

\uadf8\ub798\ud504\ub294 \ub178\ub4dc(\uc815\uc810)\uc640 \uc5e3\uc9c0(\uac04\uc120)\ub85c \uad6c\uc131\ub41c \uc790\ub8cc\uad6c\uc870\uc785\ub2c8\ub2e4. \ub178\ub4dc\ub294 \uac1d\uccb4\ub97c \ub098\ud0c0\ub0b4\uba70, \uc5e3\uc9c0\ub294 \ub178\ub4dc \uac04\uc758 \uad00\uacc4\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uadf8\ub798\ud504\ub294 \ubc29\ud5a5\uc131\uc5d0 \ub530\ub77c \ubc29\ud5a5 \uadf8\ub798\ud504\uc640 \ubb34\ud5a5 \uadf8\ub798\ud504\ub85c \ub098\ub20c \uc218 \uc788\uc73c\uba70, \uac00\uc911\uce58 \uc5ec\ubd80\uc5d0 \ub530\ub77c \uac00\uc911 \uadf8\ub798\ud504\uc640 \ube44\uac00\uc911 \uadf8\ub798\ud504\ub85c \ub098\ub20c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n

\uadf8\ub798\ud504\uc758 \ud45c\ud604 \ubc29\ubc95<\/h3>\n

\uadf8\ub798\ud504\ub294 \ub2e4\uc591\ud55c \ubc29\ubc95\uc73c\ub85c \ud45c\ud604\ud560 \uc218 \uc788\uc73c\uba70, \uac00\uc7a5 \ud754\ud55c \ub450 \uac00\uc9c0 \ubc29\ubc95\uc740 \uc778\uc811 \ud589\ub82c(Adjacency Matrix)\uacfc \uc778\uc811 \ub9ac\uc2a4\ud2b8(Adjacency List)\uac00 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n

1. \uc778\uc811 \ud589\ub82c<\/h4>\n

\uc778\uc811 \ud589\ub82c\uc740 N x N \ud06c\uae30\uc758 2\ucc28\uc6d0 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \ud45c\ud604\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. N\uc740 \uadf8\ub798\ud504\uc758 \ub178\ub4dc \uc218\uc774\uba70, \ud589\ub82c\uc758 \uac01 \uc694\uc18c\ub294 \ub178\ub4dc \uac04\uc758 \uc5f0\uacb0 \uc5ec\ubd80\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ub178\ub4dc A\uc640 \ub178\ub4dc B\uac00 \uc5f0\uacb0\ub418\uc5b4 \uc788\ub2e4\uba74, matrix[A][B]\ub294 1\uc774 \ub429\ub2c8\ub2e4.<\/p>\n

\n    fun createAdjacencyMatrix(vertices: Int, edges: List>): Array> {\n        val matrix = Array(vertices) { Array(vertices) { 0 } }\n        for (edge in edges) {\n            val (from, to) = edge\n            matrix[from][to] = 1\n            matrix[to][from] = 1  \/\/ \ubb34\ud5a5 \uadf8\ub798\ud504\uc758 \uacbd\uc6b0\n        }\n        return matrix\n    }\n    <\/array<\/pair<\/pre>\n
2. \uc778\uc811 \ub9ac\uc2a4\ud2b8<\/h4>\n
\uc778\uc811 \ub9ac\uc2a4\ud2b8\ub294 \uac01 \ub178\ub4dc\uc5d0 \ub300\ud574 \uc5f0\uacb0\ub41c \ub178\ub4dc\ub97c \uc800\uc7a5\ud558\ub294 \ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \uc774 \ubc29\uc2dd\uc740 \uba54\ubaa8\ub9ac \uc0ac\uc6a9 \uba74\uc5d0\uc11c \ud6a8\uc728\uc801\uc774\uba70, \ub178\ub4dc \uc218\uac00 \uc801\uac70\ub098 \uac04\uc120 \uc218\uac00 \uc801\uc740 \uadf8\ub798\ud504\uc5d0\uc11c \uc720\ub9ac\ud569\ub2c8\ub2e4.<\/p>\n
\n    fun createAdjacencyList(vertices: Int, edges: List>): List> {\n        val list = MutableList(vertices) { mutableListOf() }\n        for (edge in edges) {\n            val (from, to) = edge\n            list[from].add(to)\n            list[to].add(from)  \/\/ \ubb34\ud5a5 \uadf8\ub798\ud504\uc758 \uacbd\uc6b0\n        }\n        return list\n    }\n    <\/int><\/mutablelist<\/pair<\/pre>\n
\ubb38\uc81c: \uce5c\uad6c \uad00\uacc4 \ub124\ud2b8\uc6cc\ud06c<\/h2>\n
\ub2e4\uc74c\uc740 \uce5c\uad6c \uad00\uacc4\ub97c \ub098\ud0c0\ub0b4\ub294 \uadf8\ub798\ud504\uc758 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n
\n
\ubb38\uc81c: N\uba85\uc758 \uc0ac\ub78c\uacfc \uadf8\ub4e4 \uc0ac\uc774\uc758 \uce5c\uad6c \uad00\uacc4\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \ub450 \uc0ac\ub78c \uc0ac\uc774\uc758 \uce5c\uad6c \uad00\uacc4\uac00 \uc874\uc7ac\ud558\ub294\uc9c0 \ud655\uc778\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624. \uce5c\uad6c \uad00\uacc4\ub294 \ubb34\ud5a5 \uadf8\ub798\ud504\ub85c \ud45c\ud604\ub41c\ub2e4. \ub2e8, \ub450 \uc0ac\ub78c\uc758 \ubc88\ud638\ub294 0\ubd80\ud130 N-1\uae4c\uc9c0 \uc5f0\uc18d\uc801\uc73c\ub85c \uc8fc\uc5b4\uc9c4\ub2e4.<\/p>\n<\/blockquote>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1. \uc785\ub825 \ud615\uc2dd \uc774\ud574<\/h3>\n
\uba3c\uc800 \uc8fc\uc5b4\uc9c0\ub294 \ub370\uc774\ud130\ub97c \uc774\ud574\ud574\uc57c \ud569\ub2c8\ub2e4. \uc785\ub825\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n