chpt5_dfs_bfs.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "68e79bb8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[5, 2, 3, 1]\n",
      "[1, 3, 2, 5]\n"
     ]
    }
   ],
   "source": [
    "# stack example\n",
    "\n",
    "stack = []\n",
    "\n",
    "# ins 5 - ins 2 - ins 3 - ins 7 - del - ins 1 - ins 4 - del\n",
    "stack.append(5)\n",
    "stack.append(2)\n",
    "stack.append(3)\n",
    "stack.append(7)\n",
    "stack.pop()\n",
    "stack.append(1)\n",
    "stack.append(4)\n",
    "stack.pop()\n",
    "\n",
    "print(stack) # 최하단 원소부터 출력\n",
    "print(stack[::-1]) # 촤상단 원소부터 출력\n",
    "\n",
    "# 파이썬에서 스택을 이용할 떈 별도의 라이브러리 사용할 필요 없음\n",
    "# 기본 리스트에서 append(), pop() 메서드를 사용하면 스택 자료구조와 동일하게 작동!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "5858672c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deque([3, 7, 1, 4])\n",
      "deque([4, 1, 7, 3])\n"
     ]
    }
   ],
   "source": [
    "# queue example\n",
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "\n",
    "queue.append(5)\n",
    "queue.append(2)\n",
    "queue.append(3)\n",
    "queue.append(7)\n",
    "queue.popleft()\n",
    "queue.append(1)\n",
    "queue.append(4)\n",
    "queue.popleft()\n",
    "\n",
    "\n",
    "print(queue) # FIFO\n",
    "queue.reverse()\n",
    "print(queue) # LIFO\n",
    "\n",
    "\n",
    "# 파이썬으로 큐를 구현할 땐 collections module에서 제공하는 deque 자료구조를 활용!\n",
    "# deque은 스택과 큐의 장점을 모두 채택한 것이데, 데이터의 삽입, 삭제 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 사용하는 것보다\n",
    "# 더 간단!\n",
    "# 더불어 대부분의 코테에서 collecitons 모듈과 같은 기본 라이브러리 사용을 허용하므로 안심하고 사용"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "dc071005",
   "metadata": {},
   "outputs": [],
   "source": [
    "# recursive function\n",
    "\n",
    "def recursive_function():\n",
    "    print('재귀함수를 호출합니다.')\n",
    "    recursive_function()\n",
    "    \n",
    "# recursive_function()\n",
    "# 위와 같이 호출하게 되면 RecursionError: maximum recursion depth exceeded while calling a Python object\n",
    "# 와 같은 오류가 출력됨. 재귀의 최대 깊이를 초과했다는 내용\n",
    "\n",
    "# 재귀함수는 수학 시간에 언급되는 프랙털 구조와 흡사!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "7bdf2a14",
   "metadata": {},
   "outputs": [],
   "source": [
    "# base of recursive function\n",
    "\n",
    "def recursive_function(i):\n",
    "    # 100번째 출력했을 떄 종료되도록 종료 조건 명시!\n",
    "    if i == 100:\n",
    "        return\n",
    "    print(i, '번째 재귀 함수에서', i + 1,'번째 재귀 함수를 호출합니다.')\n",
    "    recursive_function(i+1)\n",
    "    print(i, '번째 재귀 함수를 종료합니다.')\n",
    "    \n",
    "# recursive_function(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "b99e623a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "720\n",
      "720\n"
     ]
    }
   ],
   "source": [
    "# 2가지 방식으로 구현한 팩토리얼 예제\n",
    "\n",
    "def factorial_iterative(n):\n",
    "    # 1부터 n까지의 수를 차례대로 곱하기!\n",
    "    result = 1\n",
    "    \n",
    "    for i in range(1, n+1):\n",
    "        result *= i\n",
    "    \n",
    "    return result\n",
    "\n",
    "def factorial_recursive(n):\n",
    "    if n <= 1: # n이 1이하인 경우 1을 반환\n",
    "        return 1\n",
    "    # n! = n*(n-1)!를 그대로 코드로 구현\n",
    "    return n*factorial_recursive(n-1)\n",
    "\n",
    "\n",
    "print(factorial_iterative(6))\n",
    "print(factorial_recursive(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "adfc32bb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 7, 5], [7, 0, 999999999], [5, 999999999, 0]]\n"
     ]
    }
   ],
   "source": [
    "# adjacent matrix in graph\n",
    "\n",
    "INF = 999999999 # 무한의 비용 선언\n",
    "\n",
    "# 2차원 리스트를 이용해 인접 행렬 표현\n",
    "graph = [\n",
    "    [0, 7, 5],\n",
    "    [7, 0, INF],\n",
    "    [5, INF, 0]\n",
    "]\n",
    "\n",
    "print(graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "521d8172",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[(1, 7), (2, 5)], [(0, 7)], [(0, 5)]]\n"
     ]
    }
   ],
   "source": [
    "# adjacent list\n",
    "\n",
    "# 행이 3개인 2차원 리스트로 인접 리스트 표현\n",
    "graph = [[] for _ in range(3)]\n",
    "\n",
    "# 노드 0에 연결된 노드 정보 저장(노드, 거리)\n",
    "graph[0].append((1, 7))\n",
    "graph[0].append((2, 5))\n",
    "\n",
    "# 노드 1에 연결된 노드 정보 저장\n",
    "graph[1].append((0, 7))\n",
    "\n",
    "# 노드 2에 연결된 노드 정보 저장\n",
    "graph[2].append((0, 5))\n",
    "\n",
    "print(graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "64a812e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 7 6 8 3 4 5  \n",
      "1 2 7 6 8 3 4 5 1\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# I implement DFS with stack and recursive function\n",
    "\n",
    "stack = []\n",
    "\n",
    "def dfs_implement(graph, i, visited):\n",
    "    visited[i] = True\n",
    "    stack.append(i)\n",
    "    print(i, end=' ')\n",
    "    for elm in graph[i]:\n",
    "        if visited[elm] == True:\n",
    "            continue\n",
    "        dfs_implement(graph, elm, visited)\n",
    "    \n",
    "    return 1\n",
    "\n",
    "\n",
    "graph = [[],\n",
    "         [2,3,8],\n",
    "         [1,7],\n",
    "         [4,5],\n",
    "         [3,5],\n",
    "         [3,4],\n",
    "         [7],\n",
    "         [2,6,8],\n",
    "         [1,7]\n",
    "]\n",
    "\n",
    "visited = [False]*9\n",
    "\n",
    "dfs_implement(graph, 1, visited)\n",
    "\n",
    "for i in range(9):\n",
    "    visited[i] = False\n",
    "    \n",
    "print(' ')\n",
    "print(dfs_implement(graph, 1, visited))\n",
    "# 내가 푼 것 : 왜 1 2 7 6 8 3 4 5 None 와 같이 출력될까? None은 무엇?\n",
    "# print(dfs_implement(graph, 1, visited)) 로 작성했기 떄문!, 전부 출력하고 **리턴값**을 출력해야 하는데 출력할게 없어서 None이 출력되는 것!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "df82b832",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 7 6 8 3 4 5 "
     ]
    }
   ],
   "source": [
    "# 책에 나온 DFS code\n",
    "\n",
    "# dfs method def\n",
    "\n",
    "def dfs(graph, v, visited):\n",
    "    # 현재 노드를 방문 처리\n",
    "    visited[v] = True\n",
    "    \n",
    "    print(v, end=' ')\n",
    "    \n",
    "    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문\n",
    "    for i in graph[v]:\n",
    "        if not visited[i]:\n",
    "            dfs(graph, i, visited)\n",
    "\n",
    "graph = [[],\n",
    "         [2,3,8],\n",
    "         [1,7],\n",
    "         [4,5],\n",
    "         [3,5],\n",
    "         [3,4],\n",
    "         [7],\n",
    "         [2,6,8],\n",
    "         [1,7]\n",
    "]\n",
    "\n",
    "visited = [False]*9\n",
    "\n",
    "dfs(graph, 1, visited) # 142p까지!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "066e0322",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "def sum(a,b):\n",
    "    print(a+b)\n",
    "    return\n",
    "\n",
    "print(sum(2, 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "edcb4c10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Visit 1 Visit 2 Visit 3 Visit 8 Visit 7 Visit 4 Visit 5 Visit 6 "
     ]
    }
   ],
   "source": [
    "# Implementation of BFS algorithm. writen by wsk\n",
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "\n",
    "def bfs_implement(graph, v, visited):\n",
    "    queue.append(v)\n",
    "    visited[v] = True\n",
    "    print('Visit', v, end=' ')\n",
    "    \n",
    "    while queue:\n",
    "        for i in graph[queue.popleft()]:\n",
    "            if not visited[i]:\n",
    "                print('Visit', i, end=' ')\n",
    "                visited[i] = True\n",
    "                queue.append(i)\n",
    "    \n",
    "\n",
    "graph = [[],\n",
    "         [2,3,8],\n",
    "         [1,7],\n",
    "         [4,5],\n",
    "         [3,5],\n",
    "         [3,4],\n",
    "         [7],\n",
    "         [2,6,8],\n",
    "         [1,7]\n",
    "]\n",
    "\n",
    "visited = [False]*9\n",
    "\n",
    "bfs_implement(graph, 1, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "2ccc4594",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 8 7 4 5 6 "
     ]
    }
   ],
   "source": [
    "# Implementation BFS in book\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "def bfs(graph, start, visited):\n",
    "    # queue 구현을 위해 deque 라이브러리 사용\n",
    "    queue = deque([start])\n",
    "    # 현재 노드를 방문 처리\n",
    "    visited[start] = True\n",
    "    # 큐가 빌 때까지 반복\n",
    "    while queue:\n",
    "        # queue에서 하나의 원소를 뽑아 출력\n",
    "        v = queue.popleft()\n",
    "        print(v, end=' ')\n",
    "        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입\n",
    "        for i in graph[v]:\n",
    "            if not visited[i]:\n",
    "                queue.append(i)\n",
    "                visited[i] = True\n",
    "                \n",
    "graph = [[],\n",
    "         [2,3,8],\n",
    "         [1,7],\n",
    "         [4,5],\n",
    "         [3,5],\n",
    "         [3,4],\n",
    "         [7],\n",
    "         [2,6,8],\n",
    "         [1,7]\n",
    "]\n",
    "\n",
    "visited = [False]*9\n",
    "\n",
    "bfs(graph, 1, visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c64303e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5\n",
      "0 1 1 1 0\n",
      "1 1 1 1 1\n",
      "1 1 1 1\n",
      "1\n",
      "0 4\n",
      "4\n",
      "[[True, True, True, True, True], [True, True, True, True, True], [True, True, True, True, True], [True, True, True, True, True]]\n"
     ]
    }
   ],
   "source": [
    "# 5-3 음료수 얼려먹기, writen by wsk, fail....\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "data = [[0]*m]*n\n",
    "\n",
    "visited = [[False]*m]*n\n",
    "\n",
    "for i in range(n):\n",
    "    data[i] = list(map(int, input().split()))\n",
    "\n",
    "# 상 하 좌 우 이동할 수 있는 방향! 미해결!\n",
    "dx = [-1, 1, 0, 0]\n",
    "dy = [0, 0, -1, 1]\n",
    "\n",
    "count = 0\n",
    "\n",
    "coord_stack = [[0]*2]*n*m\n",
    "\n",
    "def AbleMaking(x, y):\n",
    "    if visited[x][y] == True: return \n",
    "    visited[x][y] = True\n",
    "    isol_cnt = 0\n",
    "    for i in range(4):\n",
    "        nx = x+dx[i]\n",
    "        ny = y+dy[i]\n",
    "        \n",
    "        \n",
    "        if nx < 0 or ny < 0 or nx >= n or ny >= m or data[nx][ny] == 1:\n",
    "            continue\n",
    "        if visited[nx][ny] == True:\n",
    "            isol_cnt += 1\n",
    "            if isol_cnt == 4: return\n",
    "            continue\n",
    "        x = nx\n",
    "        y = ny\n",
    "        \n",
    "        print(x, y)\n",
    "        visited[x][y] = True\n",
    "        AbleMaking(x, y)\n",
    "    \n",
    "\n",
    "\n",
    "def findZero():\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            if not visited[i][j]:\n",
    "                global count\n",
    "                AbleMaking(i, j)\n",
    "                count+=1\n",
    "\n",
    "findZero()\n",
    "print(count)\n",
    "print(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "e0509fea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5\n",
      "0 0 1 1 0\n",
      "0 0 0 1 1\n",
      "1 1 1 1 1\n",
      "0 0 0 0 0\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# 5-3 음료수 얼려먹기 답안\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "graph = []\n",
    "for i in range(n):\n",
    "    graph.append(list(map(int, input().split())))\n",
    "\n",
    "# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문\n",
    "\n",
    "def dfs(x, y):\n",
    "    # 주어진 범위를 벗어나는 경우에는 즉시 종료\n",
    "    if x <= -1 or x >= n or y <= -1 or y >= m:\n",
    "        return False\n",
    "    # 현재 노드를 아직 방문하지 않았다면\n",
    "    if graph[x][y] == 0:\n",
    "    # 해당 노드 방문 처리\n",
    "        graph[x][y] = 1\n",
    "        # 상, 하, 좌, 우의 위치도 모두 재귀적으로 호출\n",
    "        dfs(x-1, y)\n",
    "        dfs(x, y-1)\n",
    "        dfs(x+1, y)\n",
    "        dfs(x, y+1)\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "result = 0\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        # 현재 위치에서 DFS 수행\n",
    "        if dfs(i, j) == True:\n",
    "            result += 1\n",
    "\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a8f0058d",
   "metadata": {},
   "outputs": [
    {
     "ename": "IndentationError",
     "evalue": "expected an indented block after function definition on line 18 (2280015107.py, line 21)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"/var/folders/kn/gg6frwt12s7gcf_n79d00hy80000gn/T/ipykernel_595/2280015107.py\"\u001b[0;36m, line \u001b[0;32m21\u001b[0m\n\u001b[0;31m    \u001b[0m\n\u001b[0m    ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m expected an indented block after function definition on line 18\n"
     ]
    }
   ],
   "source": [
    "#  5-4 미로 탈출 fail..\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "data = []\n",
    "for i in range(n):\n",
    "    data.append(list(map(int, input().split())))\n",
    "\n",
    "x, y = 1, 1\n",
    "\n",
    "visited = [[False]*m]*n\n",
    "visited[x][y] = True\n",
    "\n",
    "def bfs(queue, x, y):\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8699e0df",
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "Interrupted by user",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m/var/folders/kn/gg6frwt12s7gcf_n79d00hy80000gn/T/ipykernel_595/763272536.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      3\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mcollections\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mdeque\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m \u001b[0mn\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mm\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmap\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mint\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minput\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msplit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      7\u001b[0m \u001b[0mgraph\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36mraw_input\u001b[0;34m(self, prompt)\u001b[0m\n\u001b[1;32m   1004\u001b[0m                 \u001b[0;34m\"raw_input was called, but this frontend does not support input requests.\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1005\u001b[0m             )\n\u001b[0;32m-> 1006\u001b[0;31m         return self._input_request(\n\u001b[0m\u001b[1;32m   1007\u001b[0m             \u001b[0mstr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprompt\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1008\u001b[0m             \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_parent_ident\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m\"shell\"\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/ipykernel/kernelbase.py\u001b[0m in \u001b[0;36m_input_request\u001b[0;34m(self, prompt, ident, parent, password)\u001b[0m\n\u001b[1;32m   1049\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1050\u001b[0m                 \u001b[0;31m# re-raise KeyboardInterrupt, to truncate traceback\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1051\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mKeyboardInterrupt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Interrupted by user\"\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1052\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1053\u001b[0m                 \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlog\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwarning\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Invalid Message:\"\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mexc_info\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mTrue\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: Interrupted by user"
     ]
    }
   ],
   "source": [
    "# 5-4 미로 탈출 답안\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "graph = []\n",
    "\n",
    "for i in range(n):\n",
    "    graph.append(list(map(int, input().split())))\n",
    "    \n",
    "dx = [-1, 1, 0, 0]\n",
    "dy = [0, 0, -1, 1]\n",
    "\n",
    "def bfs(x, y):\n",
    "    # deque\n",
    "    queue = deque()\n",
    "    queue.append((x, y))\n",
    "    \n",
    "    while queue:\n",
    "        x, y = queue.popleft()\n",
    "        for i in range(4):\n",
    "            nx = x + dx[i]\n",
    "            ny = y + dy[i]\n",
    "            \n",
    "            if nx < 0 or ny < 0 or nx >= n or ny >= m:\n",
    "                continue\n",
    "            if graph[nx][ny] == 0:\n",
    "                continue\n",
    "            if graph[nx][ny] == 1:\n",
    "                graph[nx][ny] = graph[x][y]+1\n",
    "                queue.append((nx, ny))\n",
    "        \n",
    "    return graph[n-1][m-1]\n",
    "\n",
    "print(bfs(0,0))\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b6b4018c",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}