{"id":26996,"date":"2024-10-27T13:42:44","date_gmt":"2024-10-27T13:42:44","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26996"},"modified":"2024-11-26T07:24:48","modified_gmt":"2024-11-26T07:24:48","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-%ea%b2%8c%ec%9e%84-%ea%b0%9c%eb%b0%9c%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/26996\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uac8c\uc784 \uac1c\ubc1c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

\uc624\ub298\uc740 \ud30c\uc774\uc36c\uc744 \ud65c\uc6a9\ud558\uc5ec \uac8c\uc784 \uac1c\ubc1c\uc744 \uc704\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud558\ub098 \ud574\uacb0\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc774 \uac15\uc88c\uc5d0\uc11c\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud1b5\ud574 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \uae30\ub974\uace0, \uc2e4\uc81c \uac8c\uc784 \uac1c\ubc1c\uc5d0 \uc801\uc6a9\ud560 \uc218 \uc788\ub294 \ub2e4\uc591\ud55c \uae30\uc220\uacfc \uac1c\ub150\uc744 \uc775\ud788\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n

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

\ubb38\uc81c: “\uc774\uc0c1\ud55c \uaca9\uc790” \uac8c\uc784<\/p>\n

\uaca9\uc790 \ud615\ud0dc\uc758 \uac8c\uc784 \ubcf4\ub4dc\uac00 \uc8fc\uc5b4\uc9c0\uace0, \uac01 \uce78\uc5d0\ub294 \uc815\uc218\uac00 \uc800\uc7a5\ub418\uc5b4 \uc788\uc2b5\ub2c8\ub2e4. \uac8c\uc784\uc5d0\uc11c \ud50c\ub808\uc774\uc5b4\ub294 \ubcf4\ub4dc\uc758 \uacbd\uacc4 \ubc14\uae65\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec, \ucd5c\ub300 3\uce78\uae4c\uc9c0 \uc774\ub3d9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ub2e8, \ud50c\ub808\uc774\uc5b4\uac00 \uc774\ub3d9\ud560 \uc218 \uc788\ub294 \uc810\uc218\ub294 \uac01 \uce78\uc758 \uac12\uc758 \ud569\uc73c\ub85c \uacc4\uc0b0\ub429\ub2c8\ub2e4. \ud50c\ub808\uc774\uc5b4\ub294 \ucd5c\uc885\uc801\uc73c\ub85c 0 \uc774\uc0c1\uc758 \uc810\uc218\ub97c \uac00\uc9c0\ub3c4\ub85d \uacbd\uacfc\ud558\ub294 \uc774\ub3d9\uc744 \uc120\ud0dd\ud574\uc57c \ud569\ub2c8\ub2e4. \uac8c\uc784 \ubcf4\ub4dc\uc758 \ubaa8\ub4e0 \uce78\uc744 \ubc29\ubb38\ud558\uba74\uc11c \uac00\ub2a5\ud55c \ucd5c\ub300 \uc810\uc218\ub97c \uad6c\ud558\uc138\uc694.<\/p>\n

\uc785\ub825<\/h2>\n
\n        \uccab \ubc88\uc9f8 \uc904: \uaca9\uc790\uc758 \ud06c\uae30 N (1 \u2264 N \u2264 10)\n        \uadf8 \ub2e4\uc74c N\uc904: \uaca9\uc790\uc758 \uac01 \uc6d0\uc18c (\u2212100 \u2264 \uc694\uc18c \u2264 100)\n    <\/pre>\n
\ucd9c\ub825<\/h2>\n
\n        \uac00\ub2a5\ud55c \ucd5c\ub300 \uc810\uc218\n    <\/pre>\n
\uc608\uc81c \uc785\ub825<\/h3>\n
\n    3\n    10 -1 2\n    -5 20 3\n    2 -3 -4\n    <\/pre>\n
\uc608\uc81c \ucd9c\ub825<\/h3>\n
\n    32\n    <\/pre>\n
\ubb38\uc81c \ubd84\uc11d<\/h2>\n
\uc774 \ubb38\uc81c\ub294 ‘DFS(Depth First Search)’ \uae30\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubaa8\ub4e0 \uac00\ub2a5\ud55c \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uace0, \uadf8 \uc911 \ucd5c\ub300 \uc810\uc218\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \uba3c\uc800, \uaca9\uc790\uc758 \uac01 \uce78\uc5d0 \ub300\ud55c \uc774\ub3d9 \uacbd\ub85c\ub97c \uc815\uc758\ud574\uc57c \ud569\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 \uaddc\uce59\uc5d0 \ub530\ub77c, \uc2dc\uc791\uc810\uc5d0\uc11c \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uc5ec \uac00\uc7a5 \ub192\uc740 \ucd1d \uc810\uc218\ub97c \ucc3e\uc544 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1. \uae30\ubcf8 \uad6c\uc870 \uc124\uc815<\/h3>\n
\ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc7ac\uadc0 \ud568\uc218\ub97c \ud1b5\ud574 DFS\ub97c \uad6c\ud604\ud569\ub2c8\ub2e4. \uc7ac\uadc0 \ud568\uc218\ub294 \ud604\uc7ac \uc704\uce58\uc5d0\uc11c \uac08 \uc218 \uc788\ub294 \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\ub294 \uc5ed\ud560\uc744 \ud569\ub2c8\ub2e4. \ub2e4\uc74c\uc740 \uae30\ubcf8 \ud2c0\uc785\ub2c8\ub2e4.<\/p>\n
def dfs(x, y, score):\n    # \ud604\uc7ac \uc704\uce58\uc5d0\uc11c \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uace0 \ucd5c\ub300 \uc810\uc218\ub97c \ubc18\ud658\ud558\ub294 \ud568\uc218\n    pass\n    <\/code><\/pre>\n
2. \uacbd\ub85c \ud0d0\uc0c9 \ub85c\uc9c1 \uad6c\ud604<\/h3>\n
\uc774\uc81c \uac01 \uce78\uc5d0\uc11c \uc0c1\ud558\uc88c\uc6b0\ub85c \uc774\ub3d9\ud560 \ub54c\uc758 \uc704\uce58\ub97c \uacc4\uc0b0\ud560 \uc218 \uc788\uc5b4\uc57c \ud569\ub2c8\ub2e4. \uc774\ub97c \uc704\ud574\uc11c \ubc29\ud5a5 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c\uc758 \ubc29\ud5a5 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
dx = [0, 1, 0, -1] # \uc88c\uc6b0\ndy = [1, 0, -1, 0] # \uc0c1\ud558<\/code><\/pre>\n
3. \uc7ac\uadc0 \ud568\uc218 \uad6c\ud604<\/h3>\n
\uc774\uc81c DFS \ud568\uc218 \uc548\uc5d0\uc11c \uc7ac\uadc0\uc801\uc73c\ub85c \uc774\ub3d9\ud558\uba70 \uc810\uc218\ub97c \uacc4\uc0b0\ud558\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4. \uaca9\uc790\uc758 \ud06c\uae30\uc640 \ud604\uc7ac \uc810\uc218\ub97c \uae30\ubc18\uc73c\ub85c \uc774\ub3d9 \uac00\ub2a5\uc131\uc744 \uccb4\ud06c\ud558\uace0, \uacbd\uacc4 \uc870\uac74\uc744 \uc124\uc815\ud569\ub2c8\ub2e4.<\/p>\n
def dfs(x, y, score, visited):\n    if x < 0 or x >= N or y < 0 or y >= N or visited[x][y]:\n        return score\n    \n    visited[x][y] = True\n    score += grid[x][y] # \ud604\uc7ac \uc810\uc218\uc5d0 \ud604\uc7ac \uc704\uce58\uc758 \uc810\uc218\ub97c \ub354\ud569\ub2c8\ub2e4.\n    \n    max_score = score\n    for i in range(4):\n        new_x = x + dx[i]\n        new_y = y + dy[i]\n        max_score = max(max_score, dfs(new_x, new_y, score, visited))\n    \n    visited[x][y] = False # \ubc31\ud2b8\ub798\ud0b9\n    return max_score<\/code><\/pre>\n
4. \uba54\uc778 \ud568\uc218 \uad6c\ud604<\/h3>\n
\ubaa8\ub4e0 \uacbd\ub85c\ub97c \uc2dc\uc791\ud558\uae30 \uc704\ud574 \uba54\uc778 \ud568\uc218\ub97c \uc815\uc758\ud574\uc57c \ud569\ub2c8\ub2e4. \uc774 \ud568\uc218\uc5d0\uc11c \uaca9\uc790\ub97c \uc785\ub825\ubc1b\uace0, DFS \ud0d0\uc0c9\uc744 \uc2dc\uc791\ud569\ub2c8\ub2e4. \ucd5c\uc885\uc801\uc73c\ub85c \ucd5c\ub300 \uc810\uc218\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
def main():\n    global grid, N\n    N = int(input())\n    grid = [list(map(int, input().split())) for _ in range(N)]\n    \n    visited = [[False]*N for _ in range(N)]\n    max_total_score = 0\n    \n    # \ubaa8\ub4e0 \uc704\uce58\uc5d0\uc11c DFS\ub97c \uc2dc\uc791\ud569\ub2c8\ub2e4.\n    for i in range(N):\n        for j in range(N):\n            max_total_score = max(max_total_score, dfs(i, j, 0, visited))\n    \n    print(max_total_score)<\/code><\/pre>\n
5. \uc804\uccb4 \ucf54\ub4dc<\/h3>\n
\ubaa8\ub4e0 \ubd80\ubd84\uc744 \ud1b5\ud569\ud55c \uc804\uccb4 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n
def dfs(x, y, score, visited):\n    if x < 0 or x >= N or y < 0 or y >= N or visited[x][y]:\n        return score\n    \n    visited[x][y] = True\n    score += grid[x][y]\n    \n    max_score = score\n    for i in range(4):\n        new_x = x + dx[i]\n        new_y = y + dy[i]\n        max_score = max(max_score, dfs(new_x, new_y, score, visited))\n    \n    visited[x][y] = False\n    return max_score\n\ndef main():\n    global grid, N\n    N = int(input())\n    grid = [list(map(int, input().split())) for _ in range(N)]\n    \n    visited = [[False]*N for _ in range(N)]\n    max_total_score = 0\n    \n    for i in range(N):\n        for j in range(N):\n            max_total_score = max(max_total_score, dfs(i, j, 0, visited))\n    \n    print(max_total_score)\n\nif __name__ == \"__main__\":\n    main()<\/code><\/pre>\n
\uacb0\ub860<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 \uac8c\uc784\uc758 \uae30\uc900 \ud658\uacbd\uc5d0\uc11c \uc5b4\ub5a4 \ubc29\ubc95\uc73c\ub85c DFS\ub97c \ud65c\uc6a9\ud558\uc5ec \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uace0 \uc810\uc218\ub97c \ucd5c\ub300\ud654\ud560 \uc218 \uc788\ub294\uc9c0\ub97c \ubc30\uc6e0\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud55c \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \uae30\ub974\uace0, \ud30c\uc774\uc36c\uc73c\ub85c \ucf54\ub529 \ubb38\uc81c\ub97c \ud574\uacb0\ud568\uc73c\ub85c\uc368 \ub354\uc6b1 \ud6a8\uacfc\uc801\uc73c\ub85c \uac8c\uc784 \uac1c\ubc1c\uc790\ub85c\uc11c\uc758 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0ac \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\ucd94\uac00\ud559\uc2b5 \uc790\ub8cc<\/h2>\n
\ub2e4\uc74c\uacfc \uac19\uc740 \uc790\ub8cc\ub97c \ucc38\uace0\ud558\uba74 \ub354\uc6b1 \uae4a\uc774 \uc788\ub294 \ud559\uc2b5\uc774 \uac00\ub2a5\ud569\ub2c8\ub2e4:<\/p>\n