이코테 2021]3. DFS & BFS

https://youtu.be/7C9RgOcvkvo

 

 

스택(stack): 선입후출

예시 코드

stack=[]

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1]) #최상단 원소부터 출력
print(stack) # 최하단 원소부터 출력

 

큐(queue)
파이썬에서 단순히 list 자료형으로도 queue를 기능적으로 구현할 수 있으나,

시간복잡도가 높아 비효율적으로 동작할 수 있기 때문에, deque 라이브러리를 사용하는게 좋다

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue=deque() # deque 객체 생성

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

 

 

 

DFS (Depth-First Search)

• 깊이 우선 탐색
• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 자료구조(또는 재귀함수)를 이용
• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다.
     방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번 과정을 수행할 수 없을때까지 반복

탐색 순서: 1 ->2 ->7 ->6 ->8 ->3 ->4 ->5

DFS 소스코드 예제

# DFS Method 정의
def dfs(graph, v, visited):
  # 현재 노드를 방문 처리
  visited[v] = True
  print(v,end=' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph=[
  [], # 인덱스 0번 : 사용X
  [2,3,8],   # 1번 노드
  [1,7],     # 2번 노드
  [1,4,5],   # 3번 노드
  [3,5],     # 4번 노드
  [3,4],     # 5번 노드
  [7],       # 6번 노드 
  [2,6,8],   # 7번 노드
  [1,7]      # 8번 노드
]
# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False]*9
# 정의된 DFS 함수 호출
dfs(graph,1,visited)

---

BFS (Breadth-First Search)

• 너비 우선 탐색
• 가까운 노드부터 우선적으로 탐색하는 알고리즘
• 큐 자료구조를 이용
• (특정 조건에서의 최단 경로 문제 해결에 효과적 방법)
• 동작 과정
  1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서
     방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  3. 더 이상 2번 과정을 수행할 수 없을 때까지 반복한다.

---

DFS/BFS 문제풀이 

 

<문제1> 음료수 얼려 먹기

내가 작성한 코드

 

해설 코드

 

# DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
  # 주어진 범위를 벗어나는 경우 : 즉시 종료
  if x<= -1 or x>=n or y<= -1 or y>=m:
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y]==0:
    # 해당 노드 방문 처리
    graph[x][y]=1
    # 상,하,좌,우의 위치들도 모두 재귀적으로 호출
    dfs(x-1,y)
    dfs(x,y-1)
    dfs(x+1,y)
    dfs(x,y+1)
    return True
  return False


# n, m을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력 받기
graph=[]
for i in range(n):
  graph.append(list(map(int,input()))) # 공백 없이 한 줄로 입력 받은 후 정수형으로 바꾼 후 리스트로 만들기

# 모든 노드(위치)에 대하여 음료수 채우기
result=0
for i in range(n):
  for j in range(m):
    # 현재 위치에서 DFS 수행
    if dfs(i,j) == True: # 처음 방문처리가 된 거라면
        result += 1 # 카운트 진행

print(result) # 정답 출력

---

<문제2> 미로 탈출

내가 작성한 코드

 

해설 코드

 

from collections import deque

def bfs(x,y):
  queue=deque()
  queue.append((x,y))

  # 큐가 비워질 때까지 반복하기
  while queue:
    x,y= queue.popleft()
    # 현재 위치에서 4가지 방향으로의 위치 확인
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      # 미로찾기 공간을 벗어난 경우 무시
      if nx<0 or nx>=n or ny<0 or ny>=m:
        continue
      # 벽인 경우 무시
      if graph[nx][ny]==0:
        continue
      # 해당 노드를 처음 방문하는 경우에만 최단거리 기록
      if graph[nx][ny]==1:
        graph[nx][ny] = graph[x][y]+ 1 # graph[x][y] : 직전 노드의 위치에서의 최단 거리 값
        queue.append((nx,ny))
  # 가장 오른쪽 아래까지의 최단 거리 반환
  return graph[n-1][m-1]
  
n,m = map(int, input().split())

graph=[]
for i in range(n):
  graph.append(list(map(int, input())))

# 이동할 네 가지 방향 정의(상,하,좌,우)
dx=[-1,1,0,0]
dy=[0,0,-1,1]

print(bfs(0,0))

---

+ 2023.01.11 DFS/ BFS 활용 문제 유형 

인용 출처: https://devuna.tistory.com/32

3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

​

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

둘 중 편한 것을 사용하시면 됩니다.

​

2) 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

 

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

 

이밖에도 

- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS