[Algorithm] 7주차 스터디 - DFS와 BFS

그래프 탐색이란 하나의 정점으로 부터 시작하여 모든 정점을 한번씩 방문하는것이다. 이때 너비를 우선으로 탐색하느냐 깊이를 우선으로 탐색하느냐에 따라 BFS와 DFS로 나눈다.

✅ BFS는 큐를 이용해 구현한다.

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.
2. 큐에서 원소를 꺼내어 그 칸에 대해 상하좌우로 인접한 칸에 대해 (3)을 진행한다.
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입한다.
4. 큐가 빌때까지 (2), (3) 반복한다.

✅ DFS는 위의 BFS와 비슷하지만 스택을 이용해 구현하거나, 혹은 재귀를 이용해 구현하는 방법이 있다.

   1️⃣ 스택을 이용해 구현하는 방법

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남긴다.
2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 (3)을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입한다.
4. 스택이 빌 때 까지 (2)번 반복한다.

   2️⃣ 재귀를 이용해 구현하는 방법

1. 시작하는 칸을 방문했다는 표시를 남긴다.
2. 시간하는 정점과 인접한 칸에 대해 (3)을 진행
3. 해당 칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 해당칸을 매개변수로 넣어 재귀를 호출한다.

 

---

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

• 1260번은 그래프를 DFS와 BFS로 탐색한 결과를 출력하는 문제이다.
• 간선이 양방향이므로 M개의 간선을 입력받아 양방향그래프를 만들어 준다.
• 방문할 수 있는 정점이 여러개인 경우 정점 번호가 작은 것을 먼저 방문해야 하는 조건이 있기 때문에 양방향 그래프를 오름차순으로 정렬해준다.
• 위에 정리된 구현방식대로 BFS와 DFS를 진행해 방문된 점을 순서대로 출력한다.

 

import sys
input = sys.stdin.readline
from collections import deque

n, m, v = map(int, input().split())

visit_dfs = [False] * (n+1)
visit_bfs = [False] * (n+1)

#양방향 그래프 만들기
edges = [[] for _ in range(n+1)]
for i in range(m):
  v1, v2 = map(int,input().split())
  edges[v1].append(v2)
  edges[v2].append(v1)
for edge in edges:
  edge.sort()

def dfs(x):
  visit_dfs[x] = True
  print(x, end=" ")
  for i in edges[x]:
    if(visit_dfs[i] == False):
      dfs(i)
      
def bfs(x):
  visit_bfs[x] = True
  dq = deque([x])
  while(dq):
    v = dq.popleft()
    print(v, end = " ")
    for i in edges[v]:
      if(visit_bfs[i] == False):
        visit_bfs[i] = True
        dq.append(i)


dfs(v)
print()
bfs(v)

 

---

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

• 그래프 상에서 1번 컴퓨터와 연결된 컴퓨터가 몇 개 인지 찾는 문제이다.
• 간선이 양방향이므로  양방향그래프를 만들어 준다.
• BFS나 DFS 둘 중 아무거나 선택하여 1번 컴퓨터와 연결된 컴퓨터가 몇 개 인지 찾는다.
• 1번 컴퓨터를 통해 바이러스에 걸린 컴퓨터 수를 구해야 하므로 그 수가 1번 컴퓨터를 포함하지 않도록 해야한다.

 

import sys
input = sys.stdin.readline
from collections import deque

computerNum = int(input())
edgeNum = int(input())

visit_dfs = [False] * (computerNum+1)

#양방향 그래프 만들기
edges = [[] for _ in range(computerNum+1)]
for i in range(edgeNum):
  v1, v2 = map(int,input().split())
  edges[v1].append(v2)
  edges[v2].append(v1)

result = 0
def dfs(x):
  global result
  visit_dfs[x] = True
  result += 1
  for i in edges[x]:
    if(visit_dfs[i] == False):
      dfs(i)
   
dfs(1)
#1번 컴퓨터의 수는 제외시켜줘야한다.
print(result-1)

 

---

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

• 위의 "바이러스" 문제에서는 시작점이 1번 컴퓨터로 정해져 있었지만 이번 문제에서는 그 시작점들도 고려해줘야 하는 문제이다.
• 전체 배추밭을 돌면서 배추가 심어져 있는 땅(= 1)이면 그 땅을 시작점으로 BFS나 DFS를 진행하여 그 땅과 연결된 배추는 배추흰지렁이가 필요 없으므로 0으로 바꿔준다.
• 전체 배추밭을 돌면서 BFS나 DFS를 진행한 수가 필요한 배추 흰지렁이의 수이다.

 

import sys
input = sys.stdin.readline
from collections import deque

dy = (1,0,-1,0)
dx = (0,1,0,-1)

def bfs(start_y, start_x):
  dq = deque()
  dq.append((start_y, start_x))
  field[start_y][start_x] = 0
  while(dq):
    y, x = dq.popleft()
    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]
      if(0<=nx<m and 0<=ny<n)
      	if(field[ny][nx] == 1):
          dq.append((ny, nx))
          field[ny][nx] = 0
   
  
for _ in range(int(input())):
  count = 0
  m, n, k = map(int, input().split())
  field = [[0] * m for _ in range(n)]
  #배추위치 입력받아 심어주기
  for i in range(k):
    x, y = map(int, input().split())
    field[y][x] = 1
  #전체 배추밭을 돌면서 배추가 심어져 있는 땅(= 1)이면 그 땅을 시작점으로 BFS나 DFS를 진행
  for y in range(n):
    for x in range(m):
      if(field[y][x] == 1):
        bfs(y, x)
        count += 1
  print(count)

 

---

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

• 위의 문제에서 더 발전한 문제이다. "유기농 배추"에서 이차원 배열이 주어졌을때 BFS나 DFS를 진행할 시작점들을 고려해 주었다면, 이 문제에서는 벽이 어디 놓이느냐에 다라 이차원 배열이 바뀐다.
• 백트래킹을 이용해 3개의 벽을 세운 이차원배열이 완성되면, 그 이차원 배열을 돌면서 바이러스가 발견되면 그 지점을 시작점으로  BFS나 DFS를 진행시켜준다.
• 이차원 배열을 다 돈 후에 바이러스가 아직 안퍼진 안전영역의 크기를 구해주고 안전영역의 최대값을 갱신해준다. 

 

import sys
input = sys.stdin.readline
from collections import deque
import copy

dy = (1,0,-1,0)
dx = (0,1,0,-1)

def bfs(start_y, start_x, tmp):
  dq = deque()
  dq.append((start_y, start_x))
  while(dq):
    y, x = dq.popleft()
    for i in range(4):
      ny = y + dy[i]
      nx = x + dx[i]
      if(0<=nx<m and 0<=ny<n):
        if(tmp[ny][nx] == 0):
          dq.append((ny, nx))
          tmp[ny][nx] = 3

def calSafeArea(tmp):
  safe_area = 0
  for y in range(n):
    for x in range(m):
      if(tmp[y][x] == 0):
        safe_area += 1
  return safe_area

def checkSafeArea():
  global maxArea
  tmp = copy.deepcopy(field)
  for y in range(n):
    for x in range(m):
      if(tmp[y][x] == 2):
        bfs(y, x, tmp)
  maxArea = max(maxArea, calSafeArea(tmp))
   
def makeWall(count):
  if(count == 3):
    checkSafeArea()
    return
  else:
    for y in range(n):
      for x in range(m):
        if(field[y][x] == 0):
          field[y][x] = 1
          makeWall(count+1)
          field[y][x] = 0


n, m = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(n)]
maxArea = 0
tmp = [[0] * m for _ in range(n)]

makeWall(0)
print(maxArea)

 

---

참고 사이트

https://blog.encrypted.gg/942

[실전 알고리즘] 0x0A강 - DFS