{"id":28025,"date":"2024-10-27T15:21:03","date_gmt":"2024-10-27T15:21:03","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28025"},"modified":"2024-11-26T07:11:36","modified_gmt":"2024-11-26T07:11:36","slug":"%ec%9e%90%eb%b0%94%ec%8a%a4%ed%81%ac%eb%a6%bd%ed%8a%b8-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b9%8a%ec%9d%b4-%ec%9a%b0%ec%84%a0-%ed%83%90%ec%83%89","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28025\/","title":{"rendered":"\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9"},"content":{"rendered":"

<\/p>\n

\ubb38\uc81c: \ubbf8\ub85c \ud0d0\uc0c9<\/h2>\n

\uc8fc\uc5b4\uc9c4 2\ucc28\uc6d0 \ubc30\uc5f4\uc5d0\uc11c \ucd9c\ubc1c\uc810 (\uc2dc\uc791\uc810)\uc5d0\uc11c \ub3c4\ucc29\uc810\uae4c\uc9c0\uc758 \uacbd\ub85c\uac00 \uc874\uc7ac\ud558\ub294\uc9c0\ub97c \ud655\uc778\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ubc30\uc5f4\uc758 \uac12\uc740 0<\/code> (\ud1b5\uacfc \uac00\ub2a5)\uacfc 1<\/code> (\ud1b5\uacfc \ubd88\uac00\ub2a5)\uc73c\ub85c \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \ucd9c\ubc1c\uc810\uc740 (0, 0)\uc774\uace0, \ub3c4\ucc29\uc810\uc740 (N-1, M-1)\uc785\ub2c8\ub2e4. \uc0c1\ud558\uc88c\uc6b0\ub85c\ub9cc \uc774\ub3d9\ud560 \uc218 \uc788\uc73c\uba70, \uacbd\ub85c\uac00 \uc874\uc7ac\ud558\uba74 true<\/code>, \uc874\uc7ac\ud558\uc9c0 \uc54a\uc73c\uba74 false<\/code>\ub97c \ubc18\ud658\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc608\uc2dc<\/h2>\n

\uc785\ub825<\/h3>\n
\n    [\n        [0, 0, 1, 0],\n        [1, 0, 1, 0],\n        [0, 0, 0, 0],\n        [0, 1, 1, 0]\n    ]\n    <\/pre>\n
\ucd9c\ub825<\/h3>\n
true<\/code><\/p>\n
\uc124\uba85<\/h3>\n
\uc704\uc758 \uc608\uc2dc\uc5d0\uc11c \ucd9c\ubc1c\uc810 (0, 0)\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec (1, 1), (2, 1), (2, 2), (2, 3), (3, 3)\uc73c\ub85c \uacbd\ub85c\ub97c \ub530\ub77c \uac00\uba74 \ub3c4\ucc29\uc810 (3, 3)\uc5d0 \ub3c4\ub2ec\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1. \uc54c\uace0\ub9ac\uc998\uc758 \uac1c\uc694<\/h3>\n
\uc774 \ubb38\uc81c\ub294 \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS) \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. DFS\ub294 \ub178\ub4dc\ub97c \ubc29\ubb38\ud560 \ub54c \uac00\ub2a5\ud55c \ud55c \uae4a\uac8c \ub4e4\uc5b4\uac14\ub2e4\uac00 \ub354 \uc774\uc0c1 \uac08 \uc218 \uc5c6\uac8c \ub418\uba74 \ub2e4\ub978 \uacbd\ub85c\ub85c \ub3cc\uc544\uc624\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc6b0\ub9ac\ub294 \uc7ac\uadc0\ub97c \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ud560 \uac83\uc785\ub2c8\ub2e4. DFS\ub97c \uc801\uc6a9\ud558\uc5ec \ubbf8\ub85c\ub97c \ud0d0\uc0c9\ud558\uace0, \ucd9c\ubc1c\uc810\uc5d0\uc11c \ub3c4\ucc29\uc810\uae4c\uc9c0 \ub3c4\ub2ec \uac00\ub2a5\ud55c\uc9c0\ub97c \ud655\uc778\ud569\ub2c8\ub2e4.<\/p>\n
2. DFS \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h3>\n
DFS\ub97c \uad6c\ud604\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\uac00 \ud544\uc694\ud569\ub2c8\ub2e4:<\/p>\n
    \n
  1. \ud604\uc7ac \uc704\uce58\uac00 \uacbd\uacc4 \ub0b4\uc5d0 \uc788\ub294\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n
  2. \ud604\uc7ac \uc704\uce58\uac00 \ud1b5\uacfc \ubd88\uac00\ub2a5\ud55c \uc9c0\uc810\uc778\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n
  3. \ud604\uc7ac \uc704\uce58\uac00 \ub3c4\ucc29\uc9c0\uc778\uc9c0 \ud655\uc778\ud569\ub2c8\ub2e4.<\/li>\n
  4. \ud604\uc7ac \uc704\uce58\ub97c \ubc29\ubb38 \ucc98\ub9ac\ud569\ub2c8\ub2e4.<\/li>\n
  5. \uc0c1\ud558\uc88c\uc6b0 \ubc29\ud5a5\uc73c\ub85c \uc7ac\uadc0\uc801\uc73c\ub85c DFS\ub97c \ud638\ucd9c\ud569\ub2c8\ub2e4.<\/li>\n
  6. \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud55c \ud6c4 \ubc29\ubb38 \ucc98\ub9ac\ub97c \ud574\uc81c\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    3. \ucf54\ub4dc \uad6c\ud604<\/h3>\n
    \ub2e4\uc74c\uc740 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \uc774\uc6a9\ud55c DFS \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n
    \nfunction isPathExists(maze) {\n    const rows = maze.length;\n    const cols = maze[0].length;\n\n    function dfs(x, y) {\n        \/\/ \uacbd\uacc4 \uc870\uac74\n        if (x < 0 || y < 0 || x >= rows || y >= cols) return false;\n        \/\/ \ud1b5\uacfc \ubd88\uac00\ub2a5\ud55c \uc9c0\uc810\n        if (maze[x][y] === 1) return false;\n        \/\/ \ub3c4\ucc29\uc9c0\n        if (x === rows - 1 && y === cols - 1) return true;\n\n        \/\/ \ud604\uc7ac \uc704\uce58 \ubc29\ubb38 \ucc98\ub9ac\n        maze[x][y] = 1;\n\n        \/\/ \uc0c1\ud558\uc88c\uc6b0 DFS \ud0d0\uc0c9\n        const found = dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1);\n\n        \/\/ \ubc29\ubb38 \ucc98\ub9ac \ud574\uc81c\n        maze[x][y] = 0;\n\n        return found;\n    }\n\n    return dfs(0, 0);\n}\n\n\/\/ \uc608\uc81c \ud14c\uc2a4\ud2b8\nconst maze = [\n    [0, 0, 1, 0],\n    [1, 0, 1, 0],\n    [0, 0, 0, 0],\n    [0, 1, 1, 0]\n];\n\nconsole.log(isPathExists(maze)); \/\/ \ucd9c\ub825: true\n<\/code><\/pre>\n
    4. \ucf54\ub4dc \uc124\uba85<\/h3>\n
    \ucf54\ub4dc\uc758 \uc8fc\uc694 \ubd80\ubd84\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n