(이코테) DFS & BFS

스택 구현 예제

DFB, BFS 활용 문제 유형

1) 모든 정점 방문 : DFS, BFS 둘다
2) 경로 특징 저장 : DFS
3) 최단거리 : BFS

파이썬 문법

• python array[::] 사용법
  arr[A:B:C] -> index A부터 index B까지 C의 간격

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) #최하단 원소부터 출력

실행결과
[1,3,2,5]
[5,2,3,1]

큐 구현 예제

from collections import deque

queue=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) #나중에 들어온 원소부터 출력

실행결과
deque([3,7,1,4])
deque([4,1,7,3])

재귀함수 예제

def rf(i):
  if i==100:
    return 
  print(i,'번째 재귀함수에서', i+1,'번째 재귀함수를 호출합니다.')
  rf(i+1)
  print(i, '번째 재귀함수를 종료합니다.')

rf(1)

팩토리얼 구현 예제

수학적으로 0!, 1!의 값은 1

#반복으로 구현한 n!
def fac(n):
  result=1
  for i in range(1,n+1):
    result*=i
  return result

#재귀적으로 구현
def fac2(n):
  if n<=1:
    return 1
  return n*fac(n-1)

print(fac(5))
print(fac2(5))

DFS

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

def dfs(g,i,v):
  v[i]=True
  print(i, end=' ')
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for j in g[i]:
    if not v[j]:
      dfs(g,j,v)

g=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7,]
]
v=[False]*9

dfs(g,1,v)

BFS

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

from collections import deque

def bfs(graph, start, visited):
  queue=deque([start])
  # 리스트로 넣어야 들어감
  visited[start]=True
  #현재 노드를 방문 처리
  while queue:
    v=queue.popleft()
    print(v,end=" ")
    #아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True
        
graph=[
  [],
  [2,3,8],
  [1,7],
  [1,4,5],
  [3,5],
  [3,4],
  [7],
  [2,6,8],
  [1,7,]
]

visited=[False]*9
bfs(graph,1,visited)