{"id":27026,"date":"2024-10-27T13:43:02","date_gmt":"2024-10-27T13:43:02","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27026"},"modified":"2024-11-26T07:24:05","modified_gmt":"2024-11-26T07:24:05","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%84%88%eb%b9%84-%ec%9a%b0%ec%84%a0-%ed%83%90%ec%83%89","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27026\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9"},"content":{"rendered":"

<\/p>\n

\n \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(Breath-First Search, BFS)\uc740 \uadf8\ub798\ud504\ub098 \ud2b8\ub9ac \ud0d0\uc0c9\uc758 \ud55c \ubc29\ubc95\uc73c\ub85c, \uc2dc\uc791 \uc815\uc810\uc5d0\uc11c \uc778\uc811\ud55c \uc815\uc810\ub4e4\uc744 \uba3c\uc800 \ubc29\ubb38\ud558\uace0, \uadf8 \ub2e4\uc74c \uc778\uc811\ud55c \uc815\uc810\ub4e4 \uc911 \uc544\uc9c1 \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740 \uc815\uc810\ub4e4\uc744 \ubc29\ubb38\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uacbd\uc6b0\uc5d0 \ub530\ub77c \ucd5c\ub2e8 \uacbd\ub85c \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c\ub3c4 \uc0ac\uc6a9\ub429\ub2c8\ub2e4. \uc624\ub298\uc740 BFS\uc758 \uae30\ucd08 \uac1c\ub150\uacfc \ud568\uaed8 \uae4a\uc774 \uc788\ub294 \ubb38\uc81c \ud480\uc774\ub97c \uc9c4\ud589\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n

\ubb38\uc81c: \ub2e8\uc9c0\ubc88\ud638\ubd99\uc774\uae30<\/h2>\n

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

\n \uc8fc\uc5b4\uc9c4 n x n \ud06c\uae30\uc758 0\uacfc 1\ub85c \uad6c\uc131\ub41c \ubc30\uc5f4\uc5d0\uc11c 1\uc740 \uc9d1\uc774 \uc788\ub294 \uacf3\uc744 \uc758\ubbf8\ud558\uace0 0\uc740 \uc9d1\uc774 \uc5c6\ub294 \uacf3\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4. \ubaa8\ub4e0 \uc9d1\uc758 \ub2e8\uc9c0\ub97c \uad6c\ubcc4\ud558\uae30 \uc704\ud558\uc5ec \uac01 \ub2e8\uc9c0\uc5d0 \uace0\uc720\ud55c \ubc88\ud638\ub97c \ubd99\uc774\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2ed\uc2dc\uc624. \ub2e8\uc9c0\uc758 \ud06c\uae30\ub294 \uac01 \ub2e8\uc9c0\uc5d0 \uc18d\ud55c \uc9d1\uc758 \uc218\ub85c \uc815\uc758\ub429\ub2c8\ub2e4.\n<\/p>\n

\uc785\ub825<\/h3>\n
\nn (1 \u2264 n \u2264 25)\n0 \ub610\ub294 1\ub85c \uad6c\uc131\ub41c n x n \ubc30\uc5f4\n<\/pre>\n
\ucd9c\ub825<\/h3>\n
\n\uac01 \ub2e8\uc9c0\uc758 \ud06c\uae30\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \ucd9c\ub825\n<\/pre>\n
\uc608\uc81c \uc785\ub825<\/h2>\n
\n7\n0 0 1 0 0 1 1\n0 0 1 0 1 1 1\n0 1 1 0 0 0 0\n0 0 0 0 1 0 0\n1 1 1 0 1 1 0\n0 0 0 0 0 0 0\n0 0 1 0 0 0 0\n<\/pre>\n
\uc608\uc81c \ucd9c\ub825<\/h2>\n
\n1\n7\n<\/pre>\n
\ubb38\uc81c \uc811\uadfc\ubc95<\/h2>\n
\n    \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 BFS \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud558\uc5ec \uadf8\ub798\ud504\ub97c \ud0d0\uc0c9\ud560 \uac83\uc785\ub2c8\ub2e4. \uc785\ub825\ub41c 2\ucc28\uc6d0 \ubc30\uc5f4\uc744 \uc21c\ud68c\ud558\uba70 \uac01 \uc9d1(1)\uc744 \ub9cc\ub098\uba74 BFS\ub97c \ud1b5\ud574 \uc5f0\uacb0\ub41c \ubaa8\ub4e0 \uc9d1\uc758 \uc218\ub97c \uc138\uc5b4 \ub2e8\uc9c0\uc758 \ud06c\uae30\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4. \ub2e4\uc74c \ub2e8\uacc4\uc5d0\uc11c BFS\uc758 \uac1c\ub150\uc744 \uc790\uc138\ud788 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS) \uac1c\ub150<\/h2>\n
\n    BFS\ub294 \ud050\ub97c \uc774\uc6a9\ud558\uc5ec \uad6c\ud604\ub429\ub2c8\ub2e4. \ub2e4\uc74c \ud504\ub85c\uc138\uc2a4\ub97c \ub530\ub985\ub2c8\ub2e4:\n<\/p>\n
    \n
  1. \uc2dc\uc791 \ub178\ub4dc\ub97c \ud050\uc5d0 \ucd94\uac00\ud558\uace0 \ubc29\ubb38 \ud45c\uc2dc\ub97c \ud569\ub2c8\ub2e4.<\/li>\n
  2. \ud050\uc5d0\uc11c \ub178\ub4dc\ub97c \uaebc\ub0b4\uace0 \uadf8 \ub178\ub4dc\uc5d0 \uc778\uc811\ud55c \ubaa8\ub4e0 \ub178\ub4dc(\uc544\uc9c1 \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740)\ub4e4\uc744 \ud050\uc5d0 \ucd94\uac00\ud558\uace0 \ubc29\ubb38 \ud45c\uc2dc\ub97c \ud569\ub2c8\ub2e4.<\/li>\n
  3. \ud050\uac00 \ube44\uc5b4\uc788\uc9c0 \uc54a\uc73c\uba74 2\ubc88\uc73c\ub85c \ub3cc\uc544\uac11\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \ucf54\ub529 \uad6c\ud604<\/h2>\n
    \n    BFS \uc54c\uace0\ub9ac\uc998\uc744 \uc801\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ucf54\ub4dc\ub97c \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
    \nfrom collections import deque\n\ndef bfs(x, y, n, graph, visited):\n    queue = deque()\n    queue.append((x, y))\n    visited[x][y] = True\n\n    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n    size = 1  # \ub2e8\uc9c0\uc758 \ud06c\uae30\ub97c \uc800\uc7a5\n\n    while queue:\n        cx, cy = queue.popleft()  # \ud604\uc7ac \uc704\uce58\n        for dx, dy in directions:\n            nx, ny = cx + dx, cy + dy\n            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny] == 1:\n                visited[nx][ny] = True\n                queue.append((nx, ny))\n                size += 1  # \uc5f0\uacb0\ub41c \uc9d1\uc758 \uc218\ub97c \uc99d\uac00\n\n    return size  # \ub2e8\uc9c0\uc758 \ud06c\uae30 \ubc18\ud658\n\ndef find_complexes(n, graph):\n    visited = [[False] * n for _ in range(n)]\n    complexes = []\n\n    for i in range(n):\n        for j in range(n):\n            if graph[i][j] == 1 and not visited[i][j]:\n                size = bfs(i, j, n, graph, visited)\n                complexes.append(size)\n\n    return sorted(complexes)  # \ud06c\uae30\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \ubc18\ud658\n\n# \uc608\uc81c \uc785\ub825\nn = 7\ngraph = [\n    [0, 0, 1, 0, 0, 1, 1],\n    [0, 0, 1, 0, 1, 1, 1],\n    [0, 1, 1, 0, 0, 0, 0],\n    [0, 0, 0, 0, 1, 0, 0],\n    [1, 1, 1, 0, 1, 1, 0],\n    [0, 0, 0, 0, 0, 0, 0],\n    [0, 0, 1, 0, 0, 0, 0]\n]\n\ncomplex_sizes = find_complexes(n, graph)\nprint(len(complex_sizes))  # \ub2e8\uc9c0\uc758 \uc218 \ucd9c\ub825\nfor size in complex_sizes:\n    print(size)  # \uac01 \ub2e8\uc9c0\uc758 \ud06c\uae30 \ucd9c\ub825\n<\/code><\/pre>\n
    \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \n    \uc704 \ucf54\ub4dc\ub294 BFS\ub97c \uc774\uc6a9\ud558\uc5ec \ub2e8\uc9c0\uc758 \ud06c\uae30\ub97c \uacc4\uc0b0\ud558\ub294 \ubc29\ubc95\uc744 \ubcf4\uc5ec\uc90d\ub2c8\ub2e4. \uc8fc\uc694 \ud568\uc218\ub294 find_complexes<\/code>\uc640 bfs<\/code>\uc785\ub2c8\ub2e4.\n<\/p>\n