\uc548\ub155\ud558\uc138\uc694! \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \uc774\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c, \ud2b9\ud788 “\ubbf8\ub85c \ud0d0\uc0c9\ud558\uae30”\uc5d0 \ub300\ud574 \uae4a\uc774 \uc788\ub294 \ud574\uc124\uc744 \uc9c4\ud589\ud558\uaca0\uc2b5\ub2c8\ub2e4. \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \ube48\ubc88\ud788 \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c \uc720\ud615 \uc911 \ud558\ub098\ub85c, \uc8fc\uc5b4\uc9c4 \ubbf8\ub85c\uc5d0\uc11c \ucd9c\ubc1c\uc810\uc5d0\uc11c \ub3c4\ucc29\uc810\uae4c\uc9c0\uc758 \uacbd\ub85c\ub97c \ucc3e\ub294 \uac83\uc774 \ubaa9\ud45c\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \ub610\ub294 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)\uc640 \uac19\uc740 \uadf8\ub798\ud504 \ud0d0\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uc801\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c:<\/strong> \uc8fc\uc5b4\uc9c4 2\ucc28\uc6d0 \ubc30\uc5f4\ub85c \uad6c\uc131\ub41c \ubbf8\ub85c\uc5d0\uc11c \uc2dc\uc791\uc810 (start)\uc5d0\uc11c \ub3c4\ucc29\uc810 (end)\uae4c\uc9c0 \ub3c4\ub2ec\ud560 \uc218 \uc788\ub294 \uacbd\ub85c\uac00 \uc874\uc7ac\ud558\ub294\uc9c0 \ud655\uc778\ud558\uc138\uc694. \ubbf8\ub85c\uc5d0\uc11c\uc758 \uacbd\ub85c\ub294 ‘0’ (\uc774\ub3d9 \uac00\ub2a5\ud55c \uacf5\uac04)\uc744 \ub530\ub77c\uac08 \uc218 \uc788\uc73c\uba70, ‘1’ (\uc7a5\uc560\ubb3c)\uc740 \uc9c0\ub098\uac08 \uc218 \uc5c6\uc2b5\ub2c8\ub2e4.<\/p>\n \uc608\ub97c \ub4e4\uc5b4, \ub2e4\uc74c\uacfc \uac19\uc740 \ubbf8\ub85c\uac00 \uc8fc\uc5b4\uc84c\ub2e4\uace0 \uac00\uc815\ud569\ub2c8\ub2e4:<\/p>\n \uc2dc\uc791\uc810\uc740 (0, 0)\uc774\uace0 \ub3c4\ucc29\uc810\uc740 (4, 4)\uc785\ub2c8\ub2e4. \uc989, \ubbf8\ub85c\ub97c \ud0d0\uc0c9\ud558\uc5ec (0, 0)\uc5d0\uc11c (4, 4)\uae4c\uc9c0 \uac08 \uc218 \uc788\ub294 \uacbd\ub85c\uac00 \uc874\uc7ac\ud558\ub294\uc9c0\ub97c \uc54c\uc544\ub0b4\uc57c \ud569\ub2c8\ub2e4.<\/p>\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \ub610\ub294 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9) \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. BFS\ub294 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ucc3e\ub294 \ub370 \uc801\ud569\ud558\uc9c0\ub9cc, \uc774 \ubb38\uc81c\uc5d0\uc11c\ub294 \uacbd\ub85c\uc758 \uc874\uc7ac \uc5ec\ubd80\ub9cc \ud655\uc778\ud560 \uac83\uc774\ubbc0\ub85c DFS\ub97c \ud1b5\ud574\ub3c4 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n 1. **\uae30\ubcf8 \uc124\uc815**: \ubbf8\ub85c\ub97c \ud0d0\uc0c9\ud558\uae30 \uc704\ud574 \ub2e4\uc74c\uacfc \uac19\uc740 \uacfc\uc815\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uc704\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub85c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798\ub294 \ubbf8\ub85c \ud0d0\uc0c9\uc744 \uc704\ud55c DFS \uc54c\uace0\ub9ac\uc998\uc758 \uad6c\uccb4\uc801\uc778 \ucf54\ub4dc\uc785\ub2c8\ub2e4:<\/p>\n \uc704\uc758 \ucf54\ub4dc\ub294 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)\ub97c \uc774\uc6a9\ud558\uc5ec \uc8fc\uc5b4\uc9c4 \ubbf8\ub85c\uc5d0\uc11c \uc2dc\uc791\uc810\uc5d0\uc11c \ub3c4\ucc29\uc810\uae4c\uc9c0\uc758 \uacbd\ub85c\ub97c \ucc3e\ub294 \uacfc\uc815\uc744 \uad6c\ud604\ud558\uace0 \uc788\uc2b5\ub2c8\ub2e4. \uc8fc\uc694 \ub2e8\uacc4\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(V+E)\uc785\ub2c8\ub2e4. \uc5ec\uae30\uc11c V\ub294 \uc815\uc810\uc758 \uc218 (\uc989, \ubbf8\ub85c\uc758 \ubaa8\ub4e0 \uc704\uce58)\uc774\uace0, E\ub294 \uac04\uc120\uc758 \uc218 (\uc989, \uac01 \uc704\uce58\uc5d0\uc11c \uc774\ub3d9 \uac00\ub2a5\ud55c \ubc29\ud5a5\uc758 \uc218)\uc785\ub2c8\ub2e4. \ucd5c\uc545\uc758 \uacbd\uc6b0 \ubaa8\ub4e0 \uc704\uce58\ub97c \ud0d0\uc0c9\ud574\uc57c \ud558\ubbc0\ub85c \uc774 \ubcf5\uc7a1\ub3c4\uac00 \ud544\uc694\ud569\ub2c8\ub2e4. \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(V)\ub85c, \ubc29\ubb38 \ubc30\uc5f4\uc744 \uc704\ud55c \uacf5\uac04\uc774 \ud544\uc694\ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.<\/p>\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \uc774\uc6a9\ud558\uc5ec \ubbf8\ub85c \ud0d0\uc0c9 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. DFS \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ubbf8\ub85c\uc758 \uacbd\ub85c \uc874\uc7ac \uc5ec\ubd80\ub97c \ud655\uc778\ud560 \uc218 \uc788\ub294 \uae30\ucd08\uc801\uc778 \ucf54\ub4dc\uc640 \uae30\ubc95\uc744 \ubc30\uc6e0\uc2b5\ub2c8\ub2e4. \uc774\ub7ec\ud55c \uc720\ud615\uc758 \ubb38\uc81c\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c, \ub2e4\uc591\ud55c \ubcc0\ud615 \ubb38\uc81c\ub97c \ud480\uc5b4\ubcf4\uba70 \uc790\uc2e0\uac10\uc744 \ud0a4\uc6cc\ubcf4\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ub354 \ubcf5\uc7a1\ud55c \ubbf8\ub85c \ud0d0\uc0c9 \ubb38\uc81c \ub610\ub294 \ub2e4\ub978 \uc720\ud615\uc758 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub8f0 \uc608\uc815\uc774\ub2c8, \ub9ce\uc740 \uad00\uc2ec \ubd80\ud0c1\ub4dc\ub9bd\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\n[\n [0, 1, 0, 0, 0],\n [0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0],\n [0, 1, 0, 0, 0],\n [0, 0, 0, 1, 0]\n]\n<\/pre>\n
\uc785\ub825 \ubc0f \ucd9c\ub825<\/h2>\n
\n
\ubb38\uc81c \ud480\uc774 \uc811\uadfc\ubc95<\/h2>\n
\uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h2>\n
\n
\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \uad6c\ud604<\/h2>\n
\nfunction isPathExist(maze, start, end) {\n const rows = maze.length;\n const cols = maze[0].length;\n\n \/\/ \uc774\ub3d9 \ubc29\ud5a5 \ubc30\uc5f4 (\uc0c1, \ud558, \uc88c, \uc6b0)\n const directions = [\n [-1, 0], \/\/ \uc0c1\n [1, 0], \/\/ \ud558\n [0, -1], \/\/ \uc88c\n [0, 1] \/\/ \uc6b0\n ];\n\n \/\/ \uc2a4\ud0dd \ucd08\uae30\ud654 \ubc0f \ubc29\ubb38 \ubc30\uc5f4 \uc124\uc815\n const stack = [start];\n const visited = Array.from({ length: rows }, () => Array(cols).fill(false));\n visited[start[0]][start[1]] = true;\n\n \/\/ DFS \ud0d0\uc0c9\n while (stack.length > 0) {\n const [x, y] = stack.pop();\n\n \/\/ \ub3c4\ucc29\uc810\uc5d0 \ub3c4\ub2ec\ud55c \uacbd\uc6b0\n if (x === end[0] && y === end[1]) {\n return true;\n }\n\n \/\/ \uac01 \ubc29\ud5a5\uc73c\ub85c \uc774\ub3d9\n for (const [dx, dy] of directions) {\n const newX = x + dx;\n const newY = y + dy;\n\n \/\/ \ubc94\uc704 \uccb4\ud06c \ubc0f \ubc29\ubb38 \ud655\uc778\n if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&\n maze[newX][newY] === 0 && !visited[newX][newY]) {\n visited[newX][newY] = true;\n stack.push([newX, newY]);\n }\n }\n }\n\n \/\/ \ub3c4\ub2ec\ud560 \uc218 \uc5c6\ub294 \uacbd\uc6b0\n return false;\n}\n\n\/\/ \ud14c\uc2a4\ud2b8\nconst maze = [\n [0, 1, 0, 0, 0],\n [0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0],\n [0, 1, 0, 0, 0],\n [0, 0, 0, 1, 0]\n];\nconsole.log(isPathExist(maze, [0, 0], [4, 4])); \/\/ true\n<\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n
\uc131\ub2a5 \ubd84\uc11d<\/h2>\n
\ub9c8\ubb34\ub9ac<\/h2>\n