프로그래머스 - 미로 탈출

미로 탈출 문제를 보고 dfs/bfs가 떠오르긴 했는데
dfs bfs 코드를 어케 짜는지 까먹었다 ..
그래서 다시 정리하기

DFS

• 깊이 우선 탐색
• 스택 자료구조 사용

1. 탐색 시작 노드를 스택에 넣고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드 꺼냄
3. 2번을 더이상 수행할 수 없을 때까지 반복

• 스택 사용해 간단하게 구현
• 스택 쓰지 않고 재귀로 구현할 수도 있음

# 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)
 
 graph = [] # 그래프를 표현하는 인접 리스트(2차원 리스트)
 visited = [] # 각 노드가 방문한 정보를 표현하는 1차원 리스트
 
 dfs(graph, 1, visited)

---

def DFS(node):
    stack = []

    stack.push(node)

    while stack:
        current = stack.pop()

        if visited[current] == True:
            continue
        visited[current] = True

        print(node)

        for e in edge[node]:
            stack.append(e)

BFS

• 너비 우선 탐색
• 큐 사용

1. 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리
3. 2번을 더 이상 수행할 수 없을 때까지 반복

from collections import deque

# BFS 메소드 정의
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차원 리스트)
visited = [] # 각 노드가 방문된 정보를 표현하는 1차원 리스트

bfs(graph, 1, visited) # bfs 함수 호출

비교

구현 방법

• DFS : 스택 혹은 재귀함수 사용
• BFS : 큐 사용

시간 복잡도

• 두 방법 모두 모든 노드를 탐색한다는 점에서 시간 복잡도는 동일

그럼 언제 뭘 쓰냐

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

   • 둘 중 어느 방법을 사용해도 상관 X

2. 경로의 특징을 저장해야 하는 문제 - DFS

   • 예를 들어 각 정점에 숫자가 있고, a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안되는 문제 등 각 경로마다 특징을 저장해야할 때 : DFS 사용!!
   • BFS는 경로의 특징을 가지지 못한다.

3. 최단 거리 구하는 문제 - BFS

   • 미로 찾기 등 최단 거리를 구할 때, BFS가 유리
   • DFS로 경로 검색할 경우 처음으로 발견되는 해답이 최단 거리가 아닐 수 있음
   • BFS는 현재 노드부터 가까운 곳부터 찾기 때문에 먼저 찾아지는 답이 최단 거리이다.

4. 검색 대상 그래프의 크기

   • 크기가 크면 DFS
   • 규모가 크지 않고, 검색 시작 시점부터 원하는 대상이 별로 멀지 않다면 BFS 고려

참고

https://sunho-doing.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS-BFS