{"id":27032,"date":"2024-10-27T13:43:05","date_gmt":"2024-10-27T13:43:05","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27032"},"modified":"2024-11-26T07:23:59","modified_gmt":"2024-11-26T07:23:59","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-%eb%8b%a4%eb%a6%ac-%eb%a7%8c%eb%93%a4%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27032\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ub2e4\ub9ac \ub9cc\ub4e4\uae30"},"content":{"rendered":"

<\/p>\n

\n
\n

\uc548\ub155\ud558\uc138\uc694, \uc5ec\ub7ec\ubd84! \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \ud30c\uc774\uc36c\uc744 \uc774\uc6a9\ud558\uc5ec \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub2e4\ub8e8\uc5b4\uc9c0\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc8fc\uc81c\ub294 ‘\ub2e4\ub9ac \ub9cc\ub4e4\uae30’\uc785\ub2c8\ub2e4. ‘\ub2e4\ub9ac \ub9cc\ub4e4\uae30’ \ubb38\uc81c\ub294 \uc2e4\uc81c\ub85c \ub2e4\uc591\ud55c \ubcc0\ud615\uc774 \uc874\uc7ac\ud558\ub294 classic \ubb38\uc81c\ub85c, \uadf8\ub798\ud504 \uc774\ub860\uacfc \uad00\ub828\ud55c \uc911\uc694\ud55c \uac1c\ub150\ub4e4\uc744 \ud3ec\ud568\ud558\uace0 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/header>\n

\n

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

\uc8fc\uc5b4\uc9c4 \uc5ec\ub7ec \uac1c\uc758 \uc12c\uc774 \uc788\uc2b5\ub2c8\ub2e4. \uac01 \uc12c\uc740 \uc11c\ub85c \ub2e4\ub978 \uc704\uce58\uc5d0 \uc788\uc73c\uba70, \uc12c\ub4e4 \uac04\uc5d0 \ub2e4\ub9ac\ub97c \uac74\uc124\ud558\ub824\uace0 \ud569\ub2c8\ub2e4. \uc774\ub54c, \ub2e4\ub9ac\ub294 \uc218\uc9c1 \ub610\ub294 \uc218\ud3c9\uc73c\ub85c\ub9cc \uac74\uc124\ud560 \uc218 \uc788\uc73c\uba70, \ub2e4\ub9ac\uac00 \uc9c1\uc120\uc73c\ub85c \ubed7\uc5b4\ub098\uac00\uc57c \ud569\ub2c8\ub2e4. \ub610\ud55c, \uac00\ub2a5\ud55c \ud55c \ub9ce\uc740 \uc12c\uc744 \uc5f0\uacb0\ud560 \uc218 \uc788\ub3c4\ub85d \ub2e4\ub9ac\uc758 \ucd1d \uae38\uc774\ub97c \ucd5c\uc18c\ud654\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n

\uc8fc\uc5b4\uc9c4 \uc12c\uc758 \uc88c\ud45c\uac00 x, y\ub85c \uc8fc\uc5b4\uc9c8 \ub54c, \ucd5c\uc18c \ub2e4\ub9ac\uc758 \ucd1d \uae38\uc774\ub97c \ucd9c\ub825\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc138\uc694.<\/p>\n

def minimum_bridge_length(islands: List[Tuple[int, int]]) -> int:\n    pass\n<\/code><\/pre>\n
\uc785\ub825<\/h3>\n
\uc12c\uc758 \uac1c\uc218 N(2 \u2264 N \u2264 10,000)\uacfc \uac01 \uc12c\uc758 \uc88c\ud45c (x, y) \ub9ac\uc2a4\ud2b8\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/p>\n
\ucd9c\ub825<\/h3>\n
\ucd5c\uc18c \ub2e4\ub9ac\uc758 \ucd1d \uae38\uc774\ub97c \uc815\uc218\ub85c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n
\n
\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n
1. \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h3>\n
\ubb38\uc81c\uc758 \ubaa9\ud45c\ub294 \uc8fc\uc5b4\uc9c4 \uc5ec\ub7ec \uac1c\uc758 \uc12c\uc744 \uc5f0\uacb0\ud558\ub294 \ucd5c\uc18c \ub2e4\ub9ac\uc758 \ucd1d \uae38\uc774\ub97c \ucc3e\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\uc758 \ud575\uc2ec\uc740 \uac01 \uc12c \uc0ac\uc774\uc758 \ub2e4\ub9ac \uae38\uc774\uac00 \uc5b4\ub5bb\uac8c \uacc4\uc0b0\ub418\ub294\uc9c0\ub97c \uc774\ud574\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \ub450 \uc12c\uc758 \uc88c\ud45c (x1, y1)\uc640 (x2, y2)\uac00 \uc788\uc744 \ub54c, \uc774\ub4e4 \uc0ac\uc774\uc758 \ub2e4\ub9ac \uae38\uc774\ub294 |x1 – x2| + |y1 – y2|\ub85c \uacc4\uc0b0\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc989, \uac01 \uc12c\uc758 x\uc88c\ud45c\uc640 y\uc88c\ud45c\uc758 \ucc28\uc774\ub97c \ud569\ud55c \uac12\uc785\ub2c8\ub2e4.<\/p>\n
2. \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h3>\n
\uc12c\ub4e4 \uac04\uc758 \ubaa8\ub4e0 \uc870\ud569\uc744 \uace0\ub824\ud558\uc5ec \ub2e4\ub9ac\ub97c \uac74\uc124\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uadf8\ub7ec\ub098 N\uc774 \ucd5c\ub300 10,000\uc774\ubbc0\ub85c \ubaa8\ub4e0 \uc870\ud569\uc744 \uace0\ub824\ud558\uba74 O(N^2) \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uac8c \ub418\uc5b4 \ud6a8\uc728\uc801\uc774\uc9c0 \uc54a\uc2b5\ub2c8\ub2e4. \ub300\uc2e0, \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac(MST) \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud558\uc5ec \ub2e4\ub9ac\ub97c \ucd5c\uc18c\ud55c\uc73c\ub85c \uc5f0\uacb0\ud560 \uc218 \uc788\ub3c4\ub85d \ud569\ub2c8\ub2e4.<\/p>\n
MST\ub97c \uad6c\uc131\ud558\uae30 \uc704\ud574 Kruskal \ub610\ub294 Prim \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc5ec\uae30\uc11c\ub294 Prim \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uadf8\ub798\ud504\uc758 \ud55c \uaf2d\uc9d3\uc810\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \uac00\uc7a5 \uc9e7\uc740 \uac04\uc120\uc744 \ud558\ub098\uc529 \ucd94\uac00\ud574\uac00\uba70 \ucd5c\uc18c \uc2e0\uc7a5 \ud2b8\ub9ac\ub97c \ub9cc\ub4dc\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/p>\n
3. Prim \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n
\uba3c\uc800, \uac01 \uc12c\uc758 \uc88c\ud45c\ub97c \uc800\uc7a5\ud558\ub294 \ub9ac\uc2a4\ud2b8\uc640 \uc5f0\uacb0 \ube44\uc6a9\uc744 \uc800\uc7a5\ud558\ub294 \uc6b0\uc120\uc21c\uc704 \ud050\ub97c \uc900\ube44\ud569\ub2c8\ub2e4. \uadf8\ub7f0 \ub2e4\uc74c, \ud55c \uc12c\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \uc5f0\uacb0\ub41c \ubaa8\ub4e0 \uc12c\uc758 \ub2e4\ub9ac \uae38\uc774\ub97c \uacc4\uc0b0\ud558\uace0, \uac00\uc7a5 \uc9e7\uc740 \uae38\uc774\uc758 \uc12c\uc744 \ucd94\uac00\ud558\ub294 \uacfc\uc815\uc744 \ubc18\ubcf5\ud569\ub2c8\ub2e4.<\/p>\n
\nimport heapq\nfrom typing import List, Tuple\n\ndef minimum_bridge_length(islands: List[Tuple[int, int]]) -> int:\n    n = len(islands)\n    visited = [False] * n\n    min_heap = []\n    \n    # \uccab \ubc88\uc9f8 \uc12c\uc5d0\uc11c \uc2dc\uc791\n    for i in range(1, n):\n        dist = abs(islands[0][0] - islands[i][0]) + abs(islands[0][1] - islands[i][1])\n        heapq.heappush(min_heap, (dist, i))\n    \n    visited[0] = True\n    total_length = 0\n    edges_used = 0\n    \n    while min_heap and edges_used < n - 1:\n        dist, island_index = heapq.heappop(min_heap)\n        \n        if visited[island_index]:\n            continue\n        \n        visited[island_index] = True\n        total_length += dist\n        edges_used += 1\n        \n        for i in range(n):\n            if not visited[i]:\n                new_dist = abs(islands[island_index][0] - islands[i][0]) + abs(islands[island_index][1] - islands[i][1])\n                heapq.heappush(min_heap, (new_dist, i))\n    \n    return total_length\n<\/code><\/pre>\n
4. \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h3>\n
\uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(E log V)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c E\ub294 \uac04\uc120\uc758 \uac1c\uc218\uc774\uace0 V\ub294 \uc815\uc810\uc758 \uac1c\uc218\uc785\ub2c8\ub2e4. \ud558\uc9c0\ub9cc \ubaa8\ub4e0 \uc870\ud569\uc744 \uace0\ub824\ud558\uc9c0 \uc54a\uace0 \uac01 \uc12c\uc744 \uae30\uc900\uc73c\ub85c \ub2e4\ub9ac\ub97c \uc0dd\uc131\ud558\uae30 \ub54c\ubb38\uc5d0, \uc2e4\uc9c8\uc801\uc778 \uc131\ub2a5\uc740 \ub354 \uc6b0\uc218\ud569\ub2c8\ub2e4.<\/p>\n
5. \uc608\uc81c<\/h3>\n
\uc774\uc81c \uc774 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc608\uc81c\ub97c \ud574\uacb0\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\nislands = [(0, 0), (1, 1), (3, 1), (4, 0)]\nprint(minimum_bridge_length(islands))  # Output: 4\n<\/code><\/pre>\n
\uc704 \uc608\uc81c\uc5d0\uc11c, (0,0)\uc5d0\uc11c (1,1)\uc758 \ub2e4\ub9ac, (1,1)\uc5d0\uc11c (3,1), \uadf8\ub9ac\uace0 (3,1)\uc5d0\uc11c (4,0)\uae4c\uc9c0 \uc5f0\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ucd1d \ub2e4\ub9ac \uae38\uc774\ub294 4\uac00 \ub429\ub2c8\ub2e4.<\/p>\n<\/section>\n