[알고리즘] 이코테 - DFS / BFS

• 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정(그래프, 트리 등의 자료구조 안에서 탐색, DFS, BFS 등)
• 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
  • e.g., 스택과 큐(이들의 함수는 삽입-Push, 삭제-Pop으로 구성)
  • 오버플로: 특정 자료 구조가 수용할 수 있는 데이터의 크기가 가득찬 상태에서 삽입 연산 수행 시(데이터가 넘쳐 흐를때)
  • 언더플로: 특정 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산 수행 시(데이터가 전혀 없는 상태)
• 스택: 박스쌓기와 같이 선입후출 구조(후입선출 구조)
  • 기본 리스트에서 append()와 pop()메서드 이용 시 스택 자료구조와 동일하게 동작
  • append(): 리스트의 가장 뒤쪽에 데이터 삽입
  • pop(): 리스트의 가장 뒤쪽에서 데이터 꺼냄
• 큐: 대기줄과 같이 나중에 온 사람일수록 나중에 들어가서 공정한 자료구조로 비유, 선입선출 구조
  • collections 모듈에서 제공하는 deque 자료구조 활용함으로써 큐를 구현
  • 데이터를 넣고 빼는 속도가 리스트에 비해 효율적이며 queue 라이브러리보다 간단
  • e.g., from collections import deque; queue=deque() -> append(), popleft()
• 재귀 함수: 자기 자신을 다시 호출하는 함수(프랙털 구조와 흡사)
  • recusionError: 재귀의 최대 깊이 초과 시 에러, 파이썬 인터프리터의 호출 횟수 제한을 넘겨간 것이다.무한 재귀 호출은 진행X
  • 종료조건 필요함: 재귀 함수의 수행은 스택 자료구조 이용, 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝나야 그 앞의 함수 호출이 종료되기 때문 -> 스택 자료구조를 활용해야 하는 알고리즘은 재귀함수를 이용해서 간편하게 구현될 수 있다.(e.g., DFS)
  • e.g., 팩토리얼 문제: n! 시 n이 1 이하가 되었을 때 함수를 종료하는 재귀함수의 형태 -> 수학의 점화식(특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것)을 소스코드로 옮긴 것으로 구현 가능

# 팩토리얼
def recursive(n):
  if n<=1:
    return 1
  else:
    return n*recursive(n-1)

print(recursive(5))

 

 

• DFS: 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 그래프: node(vertex)와 edge로 표현되는 구조 -> 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다(이때 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다라고 표현)
  • 그래프 표현 방식: 인접 행렬, 2차원 배열로 그래프의 연결관계를 표현한다
    • 연결되지 않은 노드끼리는 무한의 비용으로 처리
    • e.g., graph=[[0,7,5],[7,0,INF],[5,INF,0]]
  • 인접 리스트: 리스트로 그래프의 연결관계를 표현하는 방식(mem 효율적, 느림)
    • 인접 리스트 자료구조를 이용해 구현한다.(리스트 자료형이 제공하는 메소드)
    • 행이 3개인 2차원 리스트로 인접 리스트 표현(노드, 거리)
    • (graph=[[] for _ in range(3)]) -> [[(1,7),(2,5)],[(0,7)],[(0,5)]]
    • 모든 인접 노드를 순회할 경우하는 경우, 더 메모리 공간 낭비가 적음
• DFS: 특정 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어서서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘
  • 과정: 탐색 시작 노드를 스택에 삽입하고 방문 처리함 -> 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리함 -> 방문하지 않은 인접 노드가 없으며 스택에서 최상단 노드를 꺼냄 -> 반복

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

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*노드개수(9)
# 정의된 DFS 함수 호출
dfs(graph,1,visited)

 

 

• BFS: 너비우선탐색, 가까운 노드부터 탐색하는 알고리즘, 선입선출방식의 큐 자료구조 사용, 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 선입선출이 되어 가까운 노드부터 탐색 진행 가능
  • 과정: 탐색 시작 노드를 큐에 삽입하고 방문 처리 -> 큐에서 노드를 꺼내 해당 녿의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.-> 반복
  • 수행시간이 더 빠르다

# BFS 메서드 정의
from collections import deque

def bfs(graph, start, visited):
  # 큐 구현을 위해 deque 라이브러리 사용
  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

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited=[False]*노드개수(9)
# 정의된 DFS 함수 호출
bfs=(graph,1,visited)

 

 

e.g., 음료수 얼려먹기: N X M 크기의 얼음 틀에서 상하좌우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주함. 얼음틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

-> DFS사용: 특정지점의 상하좌우에서 0이면서 방문하지 않는 지점을 방문 -> 방문지점에서 상하좌우를 살펴보며 방문 진쟁으로 연결된 모든 지점 방문 가능 -> 모든노드에 반복함으로써 방문하지 않은 지점의 수 세기

 

# 음료수 얼려 먹기
# DFS 메서드 정의
def dfs(x,y):
  if x<=-1 or y<=-1 or x>=n 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=map(int,input().split())
graph=[]
for i in range(n):
  graph.append(list(map(int,input())))

answer=0
for i in range(n):
  for j in range(m):
    if dfs(i,j)==True:
      answer+=1

print(answer)

 

 

e.g., N X M 크기의 직사각형 미로에서 괴물을 피해 탈출하기 위해 움직여야 하는 최소 칸의 개수 구하기

-> BFS(시작지점부터 가까운 노드부터 차례대로 그래프의 모든 노드 탐색)

-> (1,1)에서 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣기 -> 특정노드 방문 시 그 이전 노드의 거리에 1을 더한 값을 넣는다

 

# BFS 메서드 정의
from collections import deque
# 미로 탈출
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]

def bfs(x,y):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue=deque()
  queue.append((x,y))

  #큐가 빌 때까지 반복
  while queue:
    #큐에서 하나의 원소를 뽑아 출력
    x,y=queue.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y

      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      if graph[nx][ny]==0:
        continue
      if graph[nx][ny]==1:
        graph[nx][ny]=graph[x][y]+1
        queue.append((nx,ny))

  return graph[n-1][m-1]

print(bfs(0,0))