{"id":27050,"date":"2024-10-27T13:43:15","date_gmt":"2024-10-27T13:43:15","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27050"},"modified":"2024-11-26T07:23:36","modified_gmt":"2024-11-26T07:23:36","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%af%b8%eb%a1%9c-%ed%83%90%ec%83%89%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27050\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ubbf8\ub85c \ud0d0\uc0c9\ud558\uae30"},"content":{"rendered":"

<\/p>\n

1. \ubb38\uc81c \uc815\uc758<\/h2>\n

\n Given a maze represented as a 2D grid, we need to find the shortest path from the start point (S) to the end point (E). The maze consists of open paths (represented by 0) and walls (represented by 1). This is a classic problem that can be solved using graph traversal techniques such as Breadth-First Search (BFS).\n <\/p>\n

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

\n \uc608\ub97c \ub4e4\uc5b4, \uc544\ub798\uc640 \uac19\uc740 \ubbf8\ub85c\uac00 \uc788\ub2e4\uace0 \uac00\uc815\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4:\n <\/p>\n

\n    [\n        [0, 0, 1, 0, 0],\n        [0, 0, 1, 0, 1],\n        [1, 0, 0, 0, 0],\n        [0, 1, 1, 1, 0],\n        [0, 0, 0, 1, 0],\n    ]\n    <\/pre>\n
\n        \uc5ec\uae30\uc11c S\ub294 \uc2dc\uc791\uc810(0,0)\uc774\uace0, E\ub294 \ub3c4\ucc29\uc810(4,4)\uc785\ub2c8\ub2e4. 0\uc740 \uc774\ub3d9 \uac00\ub2a5\ud55c \uacbd\ub85c\ub97c, 1\uc740 \ubcbd\uc744 \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uc774 \ubbf8\ub85c\uc5d0\uc11c S\uc5d0\uc11c E\ub85c \uac00\ub294 \uac00\uc7a5 \uc9e7\uc740 \uacbd\ub85c\ub97c \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.\n    <\/p>\n
3. \uc54c\uace0\ub9ac\uc998 \uc120\uc815<\/h2>\n
\n        \ubbf8\ub85c \ud0d0\uc0c9 \ubb38\uc81c\ub294 \uc5ec\ub7ec \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc9c0\ub9cc, \uac00\uc7a5 \uc801\ud569\ud55c \uc54c\uace0\ub9ac\uc998\uc740 BFS\uc785\ub2c8\ub2e4. BFS\ub294 \uc77c\ub2e8\uc758 \ub178\ub4dc\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \uc778\uc811\ud55c \ub178\ub4dc\ub97c \ud0d0\uc0c9\ud558\uba74\uc11c \ucd5c\ub2e8 \uacbd\ub85c\ub97c \ubcf4\uc7a5\ud569\ub2c8\ub2e4. \uc774\ub294 \ubbf8\ub85c\uc758 \uc9c0\ud615\uc774 \uaca9\uc790\ud615\uc73c\ub85c \ub418\uc5b4 \uc788\ub294 \uacbd\uc6b0 \uc774\uc0c1\uc801\uc778 \uc120\ud0dd\uc785\ub2c8\ub2e4.\n    <\/p>\n
4. \ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
4.1 BFS \uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h3>\n
\n        BFS\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc9c4\ud589\ub429\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 \ud558\ub098\uc529 \uaebc\ub0b4\uc5b4 \uc778\uc811\ud55c \ub178\ub4dc\ub4e4\uc744 \ud0d0\uc0c9\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uc778\uc811\ud55c \ub178\ub4dc\uac00 \ubaa9\uc801\uc9c0 \uc774\uac70\ub098 \ubc29\ubb38\ud558\uc9c0 \uc54a\uc740 \ub178\ub4dc\uc778 \uacbd\uc6b0, \ud050\uc5d0 \ucd94\uac00\ud558\uace0 \ubc29\ubb38 \ud45c\uc2dc\ub97c \ud569\ub2c8\ub2e4.<\/li>\n
  4. \ubaa9\uc801\uc9c0\uc5d0 \ub3c4\ucc29\ud558\uba74 \ud0d0\uc0c9\uc744 \uc885\ub8cc\ud558\uace0 \uacbd\ub85c\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    4.2 \ucf54\ub4dc \uad6c\ud604<\/h3>\n
    \n        \uc544\ub798\ub294 BFS \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud55c \ubbf8\ub85c \ud0d0\uc0c9 \ucf54\ub4dc\uc785\ub2c8\ub2e4:\n    <\/p>\n
    \ndef min_steps_in_maze(maze):\n    from collections import deque\n    \n    # Directions for moving in the maze\n    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n    \n    rows, cols = len(maze), len(maze[0])\n    start = (0, 0)  # Start point\n    end = (rows - 1, cols - 1)  # End point\n    \n    # Initialize the queue for BFS\n    queue = deque([(start, 0)])  # (position, current steps)\n    visited = set()  # To keep track of visited cells\n    visited.add(start)\n    \n    while queue:\n        current_position, steps = queue.popleft()\n        \n        # Check if we reached the end\n        if current_position == end:\n            return steps\n        \n        for direction in directions:\n            new_row = current_position[0] + direction[0]\n            new_col = current_position[1] + direction[1]\n            new_position = (new_row, new_col)\n            \n            # Check if the new position is valid and not visited\n            if 0 <= new_row < rows and 0 <= new_col < cols and \\\n               maze[new_row][new_col] == 0 and new_position not in visited:\n                \n                visited.add(new_position)\n                queue.append((new_position, steps + 1))\n    \n    return -1  # Return -1 if there is no path\n    <\/pre>\n
    4.3 \ucf54\ub4dc \uc124\uba85<\/h3>\n
    \n        \uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c:<\/p>\n