[Algorithm] 탐색 알고리즘 DFS/BFS

DFS (Depth-First-Search) 

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다.

DFS의 장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있다.

DFS의 단점

• 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용한다.
• DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문이다.

BFS (Breadth-First-Search)

너비 우선 탐색이라고도 부르며 가까운 노드부터 탐색하는 알고리즘이다.

BFS 사용예시

• 웹 크롤링 - 동적으로 생성되는 무한한 인터넷 페이지를 구글이 크롤링 하기 위해서는 BFS를 합니다.
• 네트워크 브로드캐스트
• 가비지 컬렉션

BFS 장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

BFS 단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

예제 1 ) 음료수 얼려먹기

N * M 크기의 얼음틀이 있다. 구멍이 뚤려있는 부분은 0 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚤려있는부분끼리 상 하 좌 우 로 붙어있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

 dfs 방식으로 풀이

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

temp = []
for i in range(n):
  temp.append(list(map(int,input())))
def dfs(x, y):
  if x <= -1 or x >= n or y >= m or y <= -1:
    return False
  if temp[x][y] == 0:
    temp[x][y] = 1
    dfs(x - 1, y)
    dfs(x + 1, y)
    dfs(x, y - 1)
    dfs(x, y + 1)
    return True
  return False

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

bfs 방식으로 풀이

from collections import deque

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

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

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs(a, b):
    ice_m = deque()
    ice_m.append((a,b))

    if graph[a][b] == 1:
        return False

    while ice_m:
        a, b = ice_m.popleft()

        graph[a][b] = 1

        for i in range(4):
            if (0 <= a+move[i][0] <= n - 1) and (0 <= b+move[i][1] <= m -1) and (graph[a+move[i][0]][b+move[i][1]] == 0):
                ice_m.append((a+move[i][0], b+move[i][1]))
    return True

answer = 0

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

예제 2) 미로 탈출

N * M 크기의 직사각형 형대의 미로가 있다. 플레이어의 위치는 (1, 1) 이고  0이 있는 부분은 지나갈 수 없고 1이 있는 부분만 통과하여 마지막 칸까지 이동하는 최소 칸의 갯수를 구하는 문제이다.

칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

from collections import deque

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

maze = []
for i in range(n):
    maze.append(list(map(int, input())))
mx = [-1, 1, 0, 0]
my = [0, 0, -1, 1]
def bfs(x, y):
  que = deque()
  que.append((x,y))
  while que:
    x, y = que.popleft()
    for i in range(4):
        nx = x + mx[i]
        ny = y + my[i]
        if nx >= n or nx < 0 or ny >= m or ny < 0:
          continue
        if maze[nx][ny] == 0:
          continue
        if maze[nx][ny] == 1:
          maze[nx][ny] = maze[x][y] + 1
          que.append((nx,ny))
  return maze[n - 1][m - 1]
print(bfs(0, 0))