{"id":26812,"date":"2024-10-27T11:52:56","date_gmt":"2024-10-27T11:52:56","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26812"},"modified":"2024-11-26T07:29:13","modified_gmt":"2024-11-26T07:29:13","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-%ec%84%b8%ec%9d%bc%ec%a6%88%eb%a7%a8%ec%9d%98-%ea%b3%a0%eb%af%bc","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/26812\/","title":{"rendered":"\uc790\ubc14 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uc138\uc77c\uc988\ub9e8\uc758 \uace0\ubbfc"},"content":{"rendered":"

<\/p>\n

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

\n N\uba85\uc758 \ub3c4\uc2dc\ub97c \uac00\uc9c4 \uc138\uc77c\uc988\ub9e8\uc774 \uc788\uace0, \uc774 \uc138\uc77c\uc988\ub9e8\uc740 \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \ud55c \ubc88\uc529 \ubc29\ubb38\ud558\uace0 \ub2e4\uc2dc \ucd9c\ubc1c \ub3c4\uc2dc\ub85c \ub3cc\uc544\uc640\uc57c \ud569\ub2c8\ub2e4.
\n \uc138\uc77c\uc988\ub9e8\uc740 \uac01 \ub3c4\uc2dc \uac04\uc758 \uac70\ub9ac \uc815\ubcf4\uac00 \uc8fc\uc5b4\uc9c0\uba70, \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \uac83\uc774 \ubaa9\ud45c\uc785\ub2c8\ub2e4.
\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ubc31\ud2b8\ub798\ud0b9, \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ub610\ub294 \ube44\ud2b8\ub9c8\uc2a4\ud06c\ub97c \uc774\uc6a9\ud55c \ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n

\uc785\ub825 \ud615\uc2dd<\/h3>\n

\n \uccab\uc9f8 \uc904\uc5d0\ub294 \ub3c4\uc2dc\uc758 \uac1c\uc218 N\uc774 \uc8fc\uc5b4\uc9c4\ub2e4. \uc774\uc5b4\uc11c N x N \ud06c\uae30\uc758 \ud589\ub82c\uc774 \uc8fc\uc5b4\uc9c0\uba70,
\n matrix[i][j]<\/code>\ub294 \ub3c4\uc2dc i\uc5d0\uc11c \ub3c4\uc2dc j\uae4c\uc9c0\uc758 \uac70\ub9ac\ub97c \ub098\ud0c0\ub0b8\ub2e4.
\n \ub2e8, matrix[i][i]<\/code>\ub294 \ud56d\uc0c1 0\uc774\ub2e4.\n <\/p>\n

\ucd9c\ub825 \ud615\uc2dd<\/h3>\n

\n \uc138\uc77c\uc988\ub9e8\uc774 \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \ud55c \ubc88\uc529 \ubc29\ubb38\ud558\uace0 \ucd9c\ubc1c\uc9c0\ub85c \ub3cc\uc544\uc624\uae30 \uc704\ud55c \ucd5c\uc18c \ube44\uc6a9\uc744 \ucd9c\ub825\ud55c\ub2e4.\n <\/p>\n

\uc608\uc81c<\/h2>\n
\n    \uc785\ub825:\n    4\n    0 10 15 20\n    10 0 35 25\n    15 35 0 30\n    20 25 30 0\n\n    \ucd9c\ub825:\n    80\n    <\/pre>\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
\n        \ubcf8 \ubb38\uc81c\ub294 \uc804\ud615\uc801\uc778 \uc678\ud310\uc6d0 \ubb38\uc81c(TSP, Traveling Salesman Problem)\ub85c,
\n        \uc138\uc77c\uc988\ub9e8\uc774 \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \ubc29\ubb38\ud55c \ub4a4 \ucd9c\ubc1c\uc9c0\ub85c \ub3cc\uc544\uc624\ub294 \uac00\uc7a5 \uc9e7\uc740 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\uc774\ub2e4.
\n        \uc774 \ubb38\uc81c\ub294 NP-\uc644\uc804 \ubb38\uc81c\ub85c, \ub3c4\uc2dc\uc758 \uc218\uac00 \ub9ce\uc544\uc9c8\uc218\ub85d \ud574\ub97c \ucc3e\uae30 \uc704\ud55c \uacc4\uc0b0\ub7c9\uc774 \uae30\ud558\uae09\uc218\uc801\uc73c\ub85c \uc99d\uac00\ud55c\ub2e4.
\n        \uc774\uc5d0 \ub530\ub77c \uc5ec\ub7ec \uac00\uc9c0 \uc811\uadfc \ubc29\ubc95\uc744 \uace0\ub824\ud560 \uc218 \uc788\ub2e4.\n    <\/p>\n
1. \ubc31\ud2b8\ub798\ud0b9(Backtracking)<\/h3>\n
\n        \ubc31\ud2b8\ub798\ud0b9\uc740 \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c, \uc7ac\uadc0\uc801\uc73c\ub85c \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uba70
\n        \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubc29\uc2dd\uc774\ub2e4. \ud558\uc9c0\ub9cc \ub3c4\uc2dc\uc758 \uc218\uac00 \ucee4\uc9c8\uc218\ub85d \uacc4\uc0b0 \uc2dc\uac04\uc774 \ub298\uc5b4\ub09c\ub2e4.\n    <\/p>\n
2. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)<\/h3>\n
\n        \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc774\uc6a9\ud55c \ubc29\ubc95\uc740 \uba54\ubaa8\uc774\uc81c\uc774\uc158 \uae30\ubc95\uc744 \ud65c\uc6a9\ud558\uc5ec \uc774\ubbf8 \uacc4\uc0b0\ub41c \uacbd\ub85c\uc758 \ucd5c\ub2e8 \uac70\ub9ac \uac12\uc744 \uc800\uc7a5
\n       \ud574 \uc911\ubcf5 \uacc4\uc0b0\uc744 \ubc29\uc9c0\ud558\ub294 \ubc29\ubc95\uc774\ub2e4.
\n        \uc774 \ubc29\ubc95\ub860\uc5d0 \ub530\ub77c \ud2b9\uc815 \ub3c4\uc2dc \uc9d1\ud569\uc5d0 \ub300\ud55c \ucd5c\uc18c \ube44\uc6a9\uc744 \uc800\uc7a5\ud558\uace0
\n        \uc11c\ube0c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uc5ec \uc804\uccb4 \ubb38\uc81c\uc758 \ud574\uacb0\ucc45\uc744 \uad6c\uc131\ud55c\ub2e4.\n    <\/p>\n
3. \ube44\ud2b8\ub9c8\uc2a4\ud06c(Bitmasking)<\/h3>\n
\n        \ube44\ud2b8\ub9c8\uc2a4\ud0b9\uc740 \ub3c4\uc2dc \uac01\uac01\uc744 \ube44\ud2b8\ub85c \ud45c\ud604\ud558\uc5ec \ubaa8\ub4e0 \ubc29\ubb38 \uc0c1\ud0dc\ub97c \uad00\ub9ac\ud558\ub294 \uae30\ubc95\uc774\ub2e4.
\n        \uc774\ub97c \ud1b5\ud574 \uc138\uc77c\uc988\ub9e8\uc774 \uc5b4\ub5a4 \ub3c4\uc2dc\ub97c \ubc29\ubb38\ud588\ub294\uc9c0\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uad00\ub9ac\ud560 \uc218 \uc788\ub2e4.
\n        \uc774 \ubc29\ubc95\uc740 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uacfc \uc870\ud569\ud558\uc5ec \uc0ac\uc6a9\ud560 \ub54c \ub9e4\uc6b0 \ud6a8\uacfc\uc801\uc774\ub2e4.\n    <\/p>\n
\uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h2>\n
1. \ube44\ud2b8\ub9c8\uc2a4\ud0b9\uc744 \uc774\uc6a9\ud55c \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d<\/h3>\n
\n    \n    import java.util.Arrays;\n\n    public class TravelingSalesman {\n        static final int INF = Integer.MAX_VALUE;\n        static int[][] dist;\n        static int[][] dp;\n        static int n;\n\n        public static void main(String[] args) {\n            \/\/ \uc785\ub825 \uc608\uc2dc\n            n = 4; \/\/ \ub3c4\uc2dc\uc758 \uac1c\uc218\n            dist = new int[][] {\n                {0, 10, 15, 20},\n                {10, 0, 35, 25},\n                {15, 35, 0, 30},\n                {20, 25, 30, 0}\n            };\n\n            \/\/ DP \ubc30\uc5f4 \ucd08\uae30\ud654\n            dp = new int[n][1 << n];\n            for (int[] row : dp) {\n                Arrays.fill(row, -1);\n            }\n\n            \/\/ \ucd5c\ub2e8 \uacbd\ub85c \uacc4\uc0b0\n            int result = tsp(0, 1);\n            System.out.println(\"\ucd5c\uc18c \ube44\uc6a9: \" + result);\n        }\n\n        static int tsp(int pos, int mask) {\n            if (mask == (1 << n) - 1) { \/\/ \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \ubc29\ubb38\ud55c \uacbd\uc6b0\n                return dist[pos][0]; \/\/ \uc2dc\uc791 \ub3c4\uc2dc\ub85c \ub3cc\uc544\uac10\n            }\n\n            if (dp[pos][mask] != -1) {\n                return dp[pos][mask]; \/\/ \uba54\ubaa8\uc774\uc81c\uc774\uc158\ub41c \uac12 \ubc18\ud658\n            }\n\n            int ans = INF;\n\n            \/\/ \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \uc21c\ud68c\n            for (int city = 0; city < n; city++) {\n                if ((mask & (1 << city)) == 0) { \/\/ \ub3c4\uc2dc\ub97c \ubc29\ubb38\ud558\uc9c0 \uc54a\uc558\ub2e4\uba74\n                    ans = Math.min(ans, dist[pos][city] + tsp(city, mask | (1 << city)));\n                }\n            }\n\n            return dp[pos][mask] = ans; \/\/ \ud604\uc7ac \uc0c1\ud0dc \uba54\ubaa8\uc774\uc81c\uc774\uc158\n        }\n    }\n    <\/code>\n    <\/pre>\n
\uacb0\ub860<\/h2>\n
\n        \ubcf8 \ubb38\uc81c\ub294 \uc138\uc77c\uc988\ub9e8\uc774 \ubaa8\ub4e0 \ub3c4\uc2dc\ub97c \ud55c \ubc88\uc529 \ubc29\ubb38\ud558\uace0 \ub2e4\uc2dc \ucd9c\ubc1c \ub3c4\uc2dc\ub85c \ub3cc\uc544\uc624\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub300\ud45c\uc801\uc778
\n        \uacbd\ub85c \ucd5c\uc801\ud654 \ubb38\uc81c\ub85c, \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \uc811\uadfc \uac00\ub2a5\ud558\ub2e4.
\n        \ube44\ud2b8\ub9c8\uc2a4\ud0b9\uacfc \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \ud65c\uc6a9\ud55c \uc774\ubc88 \uad6c\ud604\uc740 \ub3c4\uc2dc \uc218\uac00 \uc801\uc744 \uacbd\uc6b0 \ube60\ub978 \uacc4\uc0b0\uc774 \uac00\ub2a5\ud558\uba70,
\n        \ub2e4\uc218\uc758 \ub3c4\uc2dc\ub97c \ucc98\ub9ac\ud558\uae30 \uc704\ud55c \ub2e4\ub978 \uae30\ubc95\uc758 \uc0ac\uc6a9\ub3c4 \uac00\ub2a5\ud558\ub2e4.
\n        \uc774\uc640 \uac19\uc740 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\ub97c \uae30\ub974\ub294 \uac83\uc774 \uc911\uc694\ud558\uba70,
\n        \ucf54\ub529 \uba74\uc811 \ub300\ube44\uc640 \uc2e4\uc81c \ud504\ub85c\uc81d\ud2b8\uc5d0\uc11c\ub3c4 \ub9e4\uc6b0 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub420 \uac83\uc774\ub2e4.\n    <\/p>\n
\ucc38\uace0 \ubb38\ud5cc<\/h4>\n