chpt5_dfs_bfs_review.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "cacbad7f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "visited :  1\n",
      "visited :  2\n",
      "visited :  7\n",
      "visited :  6\n",
      "visited :  8\n",
      "visited :  3\n",
      "visited :  4\n",
      "visited :  5\n"
     ]
    }
   ],
   "source": [
    "graph = [\n",
    "    [],\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",
    "]\n",
    "visited = [False]*9\n",
    "\n",
    "# 1. 처음 시작 노드의 번호를 스택에 넣는다.\n",
    "# 2. 인접한 노드 중 방문하지 않은 노드가 있다면 stack에 넣는다.\n",
    "# 3. 만약 현재 노드에서 방문할 노드가 없다면 pop을 진행한다.\n",
    "\n",
    "# 굳이 스택을 이용하지 않아도 진행됨!\n",
    "# 만약 현재 노드에서 방문하지 않은 게 있다면 재귀적으로 그 노드로 시작하는 DFS 호출\n",
    "\n",
    "def DFS(graph, start):\n",
    "    visited[start] = True\n",
    "    print(\"visited : \", start)\n",
    "    \n",
    "    for i in graph[start]:\n",
    "        if not visited[i]:\n",
    "            DFS(graph, i)\n",
    "    \n",
    "            \n",
    "    \n",
    "    return None\n",
    "\n",
    "\n",
    "DFS(graph, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "1894ca8d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "visited :  1\n",
      "visited :  2\n",
      "visited :  3\n",
      "visited :  8\n",
      "visited :  7\n",
      "visited :  4\n",
      "visited :  5\n",
      "visited :  6\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "# BFS implementation\n",
    "\n",
    "# 1. 탐색 시작 노드를 큐에 삽입\n",
    "# 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드가 있다면 모두 큐에 삽입\n",
    "# 3. 2번의 과정을 더이상 반복할 수 없을 때까지 반복\n",
    "\n",
    "queue = deque()\n",
    "\n",
    "def BFS(graph, start):\n",
    "    visited[start] = True\n",
    "    print(\"visited : \", start)\n",
    "    queue.append(start)\n",
    "    \n",
    "    while len(queue)>0:\n",
    "        for i in graph[queue.popleft()]:\n",
    "            if not visited[i]:\n",
    "                print(\"visited : \", i)\n",
    "                queue.append(i)\n",
    "                visited[i] = True\n",
    "    return None\n",
    "    \n",
    "    \n",
    "graph = [\n",
    "    [],\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",
    "]\n",
    "visited = [False]*9\n",
    "\n",
    "BFS(graph,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "1f1e154a",
   "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",
      "0 1\n",
      "1 0\n",
      "1 1\n",
      "1 2\n",
      "[[True, True, False, False, False], [True, True, True, False, False], [False, False, False, False, False], [False, False, False, False, False]]\n",
      "[[True, True, False, False, True], [True, True, True, False, False], [False, False, False, False, False], [False, False, False, False, False]]\n",
      "3 1\n",
      "3 2\n",
      "3 3\n",
      "3 4\n",
      "[[True, True, False, False, True], [True, True, True, False, False], [False, False, False, False, False], [True, True, True, True, True]]\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# 5-3 / 실전 문제 / 음료수 얼려 먹기\n",
    "from collections import deque\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "array = []\n",
    "\n",
    "for i in range(n):\n",
    "    array.append(list(map(int, input().split())))\n",
    "\n",
    "visited = [[False]*m for _ in range(n)]\n",
    "\n",
    "dx = [0, -1, 0, 1]\n",
    "dy = [-1, 0, 1, 0]\n",
    "\n",
    "queue = deque()\n",
    "\n",
    "def baverage(array, x, y):\n",
    "    global queue\n",
    "    \n",
    "    visited[x][y] = True\n",
    "    queue.append((x,y))\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",
    "            if nx < 0 or ny < 0 or nx >= n or ny >= m:\n",
    "                continue\n",
    "            if array[nx][ny] == 1 or visited[nx][ny]:\n",
    "                continue\n",
    "            visited[nx][ny] = True\n",
    "            queue.append((nx,ny))\n",
    "    \n",
    "    return 1\n",
    "        \n",
    "count = 0\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        if array[i][j] == 0 and not visited[i][j]:\n",
    "            count += baverage(array, i, j)\n",
    "            \n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f5b7ce69",
   "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",
      "[[True, True, False, False, True], [True, True, True, False, False], [False, False, False, False, False], [True, True, True, True, True]]\n"
     ]
    }
   ],
   "source": [
    "# 8-3 written by author, by using dfs, recursive function!\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "\n",
    "array = []\n",
    "for i in range(n):\n",
    "    array.append(list(map(int, input().split())))\n",
    "\n",
    "visited = [[False]*m for _ in range(n)]\n",
    "\n",
    "\n",
    "\n",
    "def dfs(array, x, y):\n",
    "    \n",
    "    if x<0 or y <0 or x>=n or y>=m:\n",
    "        return False\n",
    "    \n",
    "    if array[x][y]==0 and visited[x][y] == False:\n",
    "        visited[x][y] = True\n",
    "        dfs(array, x-1, y)\n",
    "        dfs(array, x, y-1)\n",
    "        dfs(array, x+1, y)\n",
    "        dfs(array, x, y+1)\n",
    "        return True\n",
    "        \n",
    "    return False\n",
    "\n",
    "\n",
    "count = 0\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        if dfs(array, i, j):\n",
    "            count+=1\n",
    "            \n",
    "            \n",
    "print(count)\n",
    "print(visited)\n",
    "# 다시 한 번 dfs로 구현해보기! 재귀함수 사용해서.\n",
    "# -> solve!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "3b3a520d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 6\n",
      "101010\n",
      "111111\n",
      "000001\n",
      "111111\n",
      "111111\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# 8-4 / 실전 문제 / 미로 탈출 written by me!\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "\n",
    "n, m = map(int, input().split())\n",
    "array = []\n",
    "\n",
    "value = [[-1]*m for _ in range(n)]\n",
    "\n",
    "for i in range (n):\n",
    "    array.append(list(input()))\n",
    "\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        array[i][j] = int(array[i][j])\n",
    "    \n",
    "x, y = 0, 0\n",
    "dx = [0, -1, 0, 1]\n",
    "dy = [-1, 0, 1, 0]\n",
    "\n",
    "queue.append((x, y))\n",
    "value[x][y] = 1\n",
    "while queue:\n",
    "    x, y = queue.popleft()\n",
    "    \n",
    "    for i in range(4):\n",
    "        nx = x + dx[i]\n",
    "        ny = y + dy[i]\n",
    "        \n",
    "        # 첫 번째 조건문 : 범위를 벗어나거나 괴물이 있어 이동할 수 없는 경우\n",
    "        \n",
    "        if nx < 0 or ny < 0 or nx >= n or ny >= m or array[nx][ny] == 0:\n",
    "            continue\n",
    "            \n",
    "        # 두 번째 조건문 : 이동할 수 있는 곳이나, 현재 노드에서 이동한 값보다 큰 경우(다른 먼 경로로 돌아온 경우)\n",
    "        \n",
    "        if value[nx][ny] != -1 and value[nx][ny] > value[x][y]+1:\n",
    "            value[nx][ny] = value[x][y] + 1\n",
    "        \n",
    "        # 세 번째 조건문 : 방문하지 않은 노드인 경우\n",
    "        \n",
    "        elif value[nx][ny] == -1:\n",
    "            value[nx][ny] = value[x][y] + 1\n",
    "        \n",
    "        else: continue\n",
    "        queue.append((nx, ny))\n",
    "\n",
    "\n",
    "print(value[n-1][m-1])\n",
    "\n",
    "# solve!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "baa1f976",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 6\n",
      "101010\n",
      "111111\n",
      "000001\n",
      "111111\n",
      "111111\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# 5-4 / written by author!\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",
    "    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))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "44fe590d",
   "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
}