\uc8fc\uc5b4\uc9c4 2D \ubc30\uc5f4\uc5d0\uc11c \uc2dc\uc791\uc810\uc5d0\uc11c \ub3c4\ucc29\uc810\uae4c\uc9c0\uc758 \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774 \ubc30\uc5f4\uc740 \ud1b5\ub85c\uc640 \uc7a5\uc560\ubb3c\ub85c \uad6c\uc131\ub418\uc5b4 \uc788\uc73c\uba70, \ud1b5\ub85c\ub294 0\uc73c\ub85c, \uc7a5\uc560\ubb3c\uc740 1\ub85c \ud45c\uc2dc\ub429\ub2c8\ub2e4.<\/p>\n
\ubaa9\ud45c\ub294 \uc8fc\uc5b4\uc9c4 \uc2dc\uc791\uc810\uc5d0\uc11c \ub3c4\ucc29\uc810\uae4c\uc9c0 \uc774\ub3d9\ud560 \uc218 \uc788\ub294 \uacbd\ub85c\uac00 \uc788\ub294\uc9c0\ub97c \ud310\ub2e8\ud558\uace0, \uac00\ub2a5\ud55c \uacbd\ub85c\ub97c \ucd9c\ub825\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774\ub3d9\uc740 \uc0c1\ud558\uc88c\uc6b0\ub85c \uac00\ub2a5\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n \uc608\uc0c1 \uacb0\uacfc: \uc774 \ubb38\uc81c\ub294 \uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS)\uc774\ub098 \ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9(BFS) \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc5ec\uae30\uc5d0\uc120 DFS\ub97c \uc0ac\uc6a9\ud558\uc5ec \uacbd\ub85c\ub97c \ucc3e\ub294 \ubc29\ubc95\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n DFS\ub294 \uac00\ub2a5\ud55c \uacbd\ub85c\ub97c \ubaa8\ub450 \ud0d0\uc0c9\ud558\uba74\uc11c \ub3c4\ucc29\uc810\uc5d0 \ub3c4\ub2ec\ud558\ub294\uc9c0 \uc5ec\ubd80\ub97c \ud310\ub2e8\ud569\ub2c8\ub2e4. \uacbd\ub85c\ub97c \ucc3e\ub294 \ub3d9\uc548 \ubc29\ubb38\ud55c \ub178\ub4dc\ub97c \uae30\ub85d\ud558\uc5ec \ubc18\ubcf5 \ubc29\ubb38\uc744 \ubc29\uc9c0\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n \uba3c\uc800, \uae30\ubcf8\uc801\uc778 \uc124\uc815\uc744 \ud1b5\ud574 \ubbf8\ub85c\uc640 \ucd9c\ubc1c\uc810 \ubc0f \ub3c4\ucc29\uc810\uc744 \uc815\uc758\ud569\ub2c8\ub2e4.<\/p>\n DFS\ub97c \ud1b5\ud574 \uacbd\ub85c\ub97c \ucc3e\ub294 \ud568\uc218\ub97c \uad6c\ud604\ud569\ub2c8\ub2e4.<\/p>\n \ucd5c\uc885\uc801\uc73c\ub85c \uacbd\ub85c \ucc3e\uae30 \ud568\uc218\ub97c \uad6c\ud604\ud558\uc5ec DFS\ub97c \ud638\ucd9c\ud569\ub2c8\ub2e4.<\/p>\n \ud568\uc218\ub97c \ud638\ucd9c\ud558\uc5ec \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n \uc774 \uae00\uc5d0\uc11c\ub294 2D \ubc30\uc5f4\uc5d0\uc11c \uacbd\ub85c\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 DFS \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud55c \ubc29\ubc95\uc744 \uc0b4\ud3b4\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uac01 \ub2e8\uacc4\uc5d0\uc11c DFS\ub97c \ud1b5\ud574 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\uace0, \uc870\uac74\uc744 \ucda9\uc871\ud558\ub294 \uacbd\uc6b0 \uacb0\uacfc\ub97c \ubc18\ud658\ud558\ub294 \uad6c\uc870\ub85c \ucf54\ub4dc\ub97c \uc791\uc131\ud558\uc600\uc2b5\ub2c8\ub2e4. \uc774\ub7ec\ud55c \uae30\ucd08\uc801\uc778 \uacbd\ub85c \ud0d0\uc0c9 \ubb38\uc81c\ub294 \ub354 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uae30\ucd08\ub85c \ud65c\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\ubb38\uc81c \uc815\uc758<\/h2>\n
\n def find_path(maze, start, end):\n \"\"\"\n :param maze: 2D list representing the maze\n :param start: Tuple of (x, y) coordinates for the start point\n :param end: Tuple of (x, y) coordinates for the end point\n :return: List of tuples representing the path or None if no path exists\n \"\"\"\n <\/pre>\n<\/section>\n
\ubb38\uc81c \uc608\uc2dc<\/h2>\n
\n maze = [\n [0, 1, 0, 0, 0],\n [0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0],\n [1, 1, 0, 0, 0],\n [0, 0, 0, 1, 1]\n ]\n start = (0, 0) # \uc2dc\uc791\uc810\n end = (4, 4) # \ub3c4\ucc29\uc810\n <\/pre>\n
\n [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]\n <\/p>\n<\/section>\n\ubb38\uc81c \ud574\uacb0 \ubc29\uc548<\/h2>\n
\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9(DFS) \uc54c\uace0\ub9ac\uc998<\/h3>\n
\uad6c\ud604 \ub2e8\uacc4<\/h2>\n
1\ub2e8\uacc4: \uae30\ubcf8 \uc124\uc815<\/h3>\n
\n maze = [\n [0, 1, 0, 0, 0],\n [0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0],\n [1, 1, 0, 0, 0],\n [0, 0, 0, 1, 1]\n ]\n start = (0, 0)\n end = (4, 4)\n <\/pre>\n
2\ub2e8\uacc4: DFS \ud568\uc218 \uc815\uc758<\/h3>\n
\n def dfs(maze, current, end, path, visited):\n if current == end:\n return path\n \n x, y = current\n visited.add(current)\n\n for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n next_x, next_y = x + dx, y + dy\n \n if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):\n if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:\n result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)\n if result is not None:\n return result\n \n visited.remove(current)\n return None\n <\/pre>\n
3\ub2e8\uacc4: \uacbd\ub85c \ucc3e\uae30 \ud568\uc218 \uad6c\ud604<\/h3>\n
\n def find_path(maze, start, end):\n visited = set()\n return dfs(maze, start, end, [start], visited)\n <\/pre>\n
4\ub2e8\uacc4: \uacb0\uacfc \ucd9c\ub825<\/h3>\n
\n path = find_path(maze, start, end)\n print(\"\uacbd\ub85c:\", path)\n <\/pre>\n<\/section>\n
\uc804\uccb4 \ucf54\ub4dc<\/h2>\n
\n def dfs(maze, current, end, path, visited):\n if current == end:\n return path\n \n x, y = current\n visited.add(current)\n\n for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n next_x, next_y = x + dx, y + dy\n \n if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]):\n if maze[next_x][next_y] == 0 and (next_x, next_y) not in visited:\n result = dfs(maze, (next_x, next_y), end, path + [(next_x, next_y)], visited)\n if result is not None:\n return result\n \n visited.remove(current)\n return None\n\n def find_path(maze, start, end):\n visited = set()\n return dfs(maze, start, end, [start], visited)\n\n maze = [\n [0, 1, 0, 0, 0],\n [0, 1, 0, 1, 0],\n [0, 0, 0, 1, 0],\n [1, 1, 0, 0, 0],\n [0, 0, 0, 1, 1]\n ]\n start = (0, 0)\n end = (4, 4)\n path = find_path(maze, start, end)\n print(\"\uacbd\ub85c:\", path)\n <\/pre>\n<\/section>\n
\uacb0\ub860<\/h2>\n