03-dfs_bfs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# basic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## stack and queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "[2]\n",
      "[2, 3]\n",
      "deque([2, 3])\n"
     ]
    }
   ],
   "source": [
    "# read data by using row number and column number\n",
    "graph = [[0,0,1],[0,0,0],[0,0,0]]\n",
    "print(graph[0][2])\n",
    "\n",
    "# stack and queue\n",
    "# conventional stack\n",
    "stack = []\n",
    "stack.append(2)\n",
    "stack.append(3)\n",
    "stack.pop()\n",
    "print(stack)\n",
    "\n",
    "# conventional queue\n",
    "queue = []\n",
    "queue.append(1)\n",
    "queue.append(2)\n",
    "queue.append(3)\n",
    "queue.pop(0)\n",
    "print(queue)\n",
    "\n",
    "# library queue\n",
    "from collections import deque\n",
    "queue = deque()\n",
    "queue.append(1)\n",
    "queue.append(2)\n",
    "queue.append(3)\n",
    "queue.popleft()\n",
    "print(queue)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[2, 3, 8]\n",
      "[1, 7]\n",
      "[1, 4, 5]\n",
      "[3, 5]\n",
      "[3, 4]\n",
      "[7]\n",
      "[2, 6, 8]\n",
      "[1, 7]\n"
     ]
    }
   ],
   "source": [
    "list_g = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7],[2,6,8],[1,7]]\n",
    "\n",
    "for i in list_g:\n",
    "  print(i)\n",
    "\n",
    "# def changeGraphForm(graph, list_graph=True):\n",
    "#   if list_graph == False:\n",
    "#     return None\n",
    "  \n",
    "#   adjacent_mat = []\n",
    "#   for i, inner_list in enumerate(list_g):\n",
    "#     lis = [0]*len(list_g)\n",
    "#     for j in inner_list:\n",
    "#       lis[j] = 1\n",
    "#     adjacent_mat.append(lis)\n",
    "\n",
    "#   return adjacent_mat\n",
    "\n",
    "\n",
    "# adjacent_mat = changeGraphForm(list_g, list_graph=True)\n",
    "# for i in adjacent_mat:\n",
    "#   print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## basic DFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 7 6 8 3 4 5 "
     ]
    }
   ],
   "source": [
    "def dfs(graph, start_node):\n",
    "  # 1. initialization \n",
    "  visited = [0] * len(graph)\n",
    "\n",
    "  stack = []\n",
    "  stack.append(start_node)\n",
    "  visited[start_node] = 1\n",
    "  print(start_node, end=' ')\n",
    "\n",
    "  while stack:\n",
    "    node = stack[-1]\n",
    "    \n",
    "    possible_visit = False\n",
    "    for n in graph[node]:\n",
    "      if not visited[n]:\n",
    "        possible_visit = True\n",
    "        stack.append(n)\n",
    "        visited[n] = 1\n",
    "        print(n, end=' ')\n",
    "\n",
    "        break\n",
    "    \n",
    "    if possible_visit == False:\n",
    "      stack.pop()\n",
    "\n",
    "dfs(list_g, 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 8 7 4 5 6 "
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "def bfs(graph, start_node):\n",
    "  visited = [0] * len(graph)  \n",
    " \n",
    "  queue = deque()\n",
    "  queue.append(start_node)\n",
    "  visited[start_node] = 1\n",
    "\n",
    "  while queue:\n",
    "    node = queue.popleft()\n",
    "    print(node, end=' ')\n",
    "\n",
    "\n",
    "    for n in graph[node]:\n",
    "      if not visited[n]:\n",
    "        queue.append(n)\n",
    "        visited[n] = 1\n",
    "      \n",
    "  \n",
    "\n",
    "\n",
    "bfs(list_g, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DFS and BFS"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:violet\">**음료수 얼려 먹기**</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 1]\n",
      "[1, 1, 1]\n",
      "[1, 1, 1]\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# example input\n",
    "# graph= [[0,0,1,1,0],[0,0,0,1,1], [1,1,1,1,1],[0,0,0,0,0]]\n",
    "# n=4\n",
    "# m=5\n",
    "\n",
    "graph = [[0,0,1],[0,1,0],[1,0,1]]\n",
    "n=3\n",
    "m=3\n",
    "\n",
    "def dfs(x, y):\n",
    "  if x<=-1 or y<=-1 or x>=n or y>=m:\n",
    "    return False\n",
    "  \n",
    "  if graph[x][y] == 0:\n",
    "    # check node\n",
    "    graph[x][y] = 1\n",
    "\n",
    "    # calling for up/down/right/left dfs\n",
    "    dfs(x, y-1)\n",
    "    dfs(x, y+1)\n",
    "    dfs(x+1, y)\n",
    "    dfs(x-1, y)\n",
    "    return True\n",
    "\n",
    "  return False\n",
    "\n",
    "\n",
    "res = 0\n",
    "# calling func\n",
    "for i in range(n):\n",
    "  for j in range(m):\n",
    "    if dfs(i,j) == True:\n",
    "      res += 1\n",
    "\n",
    "\n",
    "# print out graph\n",
    "for i in graph:\n",
    "  print(i)\n",
    "\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "not enough values to unpack (expected 2, got 0)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-5-efea659a7730>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\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      2\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[1;32m      3\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\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      4\u001b[0m   \u001b[0mgraph\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlist\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[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mValueError\u001b[0m: not enough values to unpack (expected 2, got 0)"
     ]
    }
   ],
   "source": [
    "n, m = map(int, input().split())\n",
    "graph=[]\n",
    "for i in range(n):\n",
    "  graph.append(list(map(int, input())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <span style=\"color:violet\">**미로탈출**</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 0]\n",
      "[0, 1, 0]\n",
      "[0, 1, 1]\n",
      "----------\n",
      "[1, 1, 0]\n",
      "[0, 1, 0]\n",
      "[0, 1, 1]\n",
      "----------\n",
      "-1 0\n",
      "1 0\n",
      "0 -1\n",
      "0 1\n",
      "deque([[0, 1]])\n",
      "[1, 2, 0]\n",
      "[0, 1, 0]\n",
      "[0, 1, 1]\n",
      "----------\n",
      "-1 1\n",
      "1 1\n",
      "0 0\n",
      "0 2\n",
      "deque([[1, 1], [0, 0]])\n",
      "[3, 2, 0]\n",
      "[0, 3, 0]\n",
      "[0, 1, 1]\n",
      "----------\n",
      "0 1\n",
      "2 1\n",
      "1 0\n",
      "1 2\n",
      "deque([[0, 0], [2, 1]])\n",
      "[3, 2, 0]\n",
      "[0, 3, 0]\n",
      "[0, 4, 1]\n",
      "----------\n",
      "-1 0\n",
      "1 0\n",
      "0 -1\n",
      "0 1\n",
      "deque([[2, 1]])\n",
      "[3, 2, 0]\n",
      "[0, 3, 0]\n",
      "[0, 4, 1]\n",
      "----------\n",
      "1 1\n",
      "3 1\n",
      "2 0\n",
      "2 2\n",
      "deque([[2, 2]])\n",
      "[3, 2, 0]\n",
      "[0, 3, 0]\n",
      "[0, 4, 5]\n",
      "----------\n",
      "1 2\n",
      "3 2\n",
      "2 1\n",
      "2 3\n",
      "deque([])\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "n = 3\n",
    "m = 3\n",
    "graph = [[1,1,0],[0,1,0],[0,1,1]]\n",
    "\n",
    "for i in graph:\n",
    "  print(i)\n",
    "print('-'*10)\n",
    "\n",
    "# [U D L R] x: row y: col\n",
    "dx = [-1,1,0,0]\n",
    "dy = [0,0,-1,1]\n",
    "\n",
    "start_point = [0, 0]\n",
    "def bfs(graph, start_point):\n",
    "  queue = deque()\n",
    "  queue.append(start_point)\n",
    "\n",
    "  while queue:\n",
    "    for i in graph:\n",
    "      print(i)\n",
    "    print('-'*10)\n",
    "\n",
    "    x, y = queue.popleft()\n",
    "\n",
    "    for i in range(4):\n",
    "      nx = x + dx[i]\n",
    "      ny = y + dy[i]\n",
    "      print(nx,ny)\n",
    "      if nx < 0 or nx >= n or ny < 0 or ny >= m:\n",
    "        continue\n",
    "\n",
    "      if graph[nx][ny] == 0:\n",
    "        continue\n",
    "\n",
    "      if graph[nx][ny] == 1:\n",
    "        graph[nx][ny] = graph[x][y]+1\n",
    "        queue.append([nx,ny])\n",
    "          \n",
    "    print(queue)\n",
    "    \n",
    "  return graph[n-1][m-1]\n",
    "\n",
    "        \n",
    "\n",
    "  \n",
    "print(bfs(graph, start_point))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 연습문제"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "특정 거리의 도시 찾기"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [(1, 2), (1, 3)], [(2, 3), (2, 4)], [], []]\n",
      "[0, 0, 1, 2, 1]\n",
      "[4]\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "n=4 # node\n",
    "m=4 # edge\n",
    "k=2 # distance\n",
    "x=1 # start\n",
    "\n",
    "inputs = [(1,2),(1,3),(2,3),(2,4)]\n",
    "\n",
    "gh = [[] for _ in range(n+1)]\n",
    "\n",
    "for a, b in inputs:\n",
    "  gh[a].append((a,b))\n",
    "\n",
    "print(gh)\n",
    "\n",
    "dist = [0] * (n+1)\n",
    "visited = [-1] * (n+1)\n",
    "\n",
    "def bfs(start):\n",
    "  queue = deque()\n",
    "  queue.append(start)\n",
    "  dist[start] = 0\n",
    "\n",
    "  while queue:\n",
    "    now = queue.popleft()\n",
    "    visited[now] = 1\n",
    "\n",
    "    for a, b in gh[now]:\n",
    "      queue.append(b)\n",
    "      dist[b] += 1\n",
    "\n",
    "  print(dist)\n",
    "  return dist\n",
    "\n",
    "distance = bfs(x)\n",
    "\n",
    "node = []\n",
    "for i, d in enumerate(distance):\n",
    "  if d == k:\n",
    "    node.append(i+1)\n",
    "print(node)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "연구소"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "ename": "UnboundLocalError",
     "evalue": "local variable 'result' referenced before assignment",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mUnboundLocalError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-16-c177166c76fe>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     43\u001b[0m         \u001b[0mcount\u001b[0m \u001b[0;34m-=\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     44\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 45\u001b[0;31m \u001b[0mdfs\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\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     46\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-16-c177166c76fe>\u001b[0m in \u001b[0;36mdfs\u001b[0;34m(count)\u001b[0m\n\u001b[1;32m     27\u001b[0m           \u001b[0mvirus\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mj\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     28\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 29\u001b[0;31m   \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmax\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mresult\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mget_score\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     30\u001b[0m   \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     31\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mUnboundLocalError\u001b[0m: local variable 'result' referenced before assignment"
     ]
    }
   ],
   "source": [
    "n = 4\n",
    "m = 6\n",
    "\n",
    "map = [[0,0,0,0,0,0],[1,0,0,0,0,2],[1,1,1,0,0,2],[0,0,0,0,0,2]]\n",
    "temp = [[0]*m for _ in range(n)]\n",
    "\n",
    "dx = [-1, 0, 1, 0]\n",
    "dy = [0, 1, 0, -1]\n",
    "\n",
    "def virus(x, y):\n",
    "  for i in range(4)\n",
    "    nx = x + dx[i]\n",
    "    ny = y + dy[i]\n",
    "\n",
    "    if nx > 0 and nx < n and ny >= 0 and ny < m:\n",
    "      temp[nx][ny]=2\n",
    "      virus(nx, ny)\n",
    "      \n",
    "  return 0\n",
    "\n",
    "def get_score():\n",
    "  score = 0\n",
    "  for i in range(n):\n",
    "    for j in range(m):\n",
    "      if temp[i][j] == 0:\n",
    "        score += 1\n",
    "  return score\n",
    "\n",
    "result = 0\n",
    "def dfs(count):\n",
    "  if count == 3:\n",
    "    for i in range(n):\n",
    "      for j in range(m):\n",
    "        if temp[i][j]==2:\n",
    "          virus(i, j)\n",
    "    \n",
    "  result = max(result, get_score())\n",
    "  return result\n",
    "\n",
    "  for i in range(n):\n",
    "    for j in range(m):\n",
    "      if map[i][j] == 0:\n",
    "        map[i][j] = 1\n",
    "        count += 1\n",
    "\n",
    "        for i in data:\n",
    "          print(i)\n",
    "\n",
    "        dfs(count)\n",
    "        map[i][j] = 0\n",
    "        count -= 1\n",
    "\n",
    "dfs(0)\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "45d80257ccf4ae77bb116447a323b4ded5c7d4f4eb3ea993cf039511269910c8"
  },
  "kernelspec": {
   "display_name": "Python 3.8.8 ('base')",
   "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.8.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}