[PS] 파이썬 BFS / DFS 구현방법

🔎DFS (Depth First Search)

깊이 우선 탐색으로, 스택을 사용해 구현한다.

구현 방법

1. graph를 배열의 형태로 완성한다.
   → 각 index에 해당 index번째 노드와 연결된 간선의 번호를 적는다.
   cf) 양방향인 경우, 양쪽에 적어야한다.
2. 탐색 시작 노드를 스택에 삽입하고 방문처리한다.
3. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리한다.
   → 방문하지 않은 인접 노드가 없으면 다시 스택에서 최상단 노드를 꺼낸다.
4. 2번이 불가능 할때까지 반복한다.

# 방문 정보를 리스트 자료형으로 표현
# 노드는 9개지만, index 0번 노드는 사용하지 않는다.
visited =[False] * 10

# 각 노드가 연결된  정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
	[],                 # 빈 자리
  [3, 4, 5],          # 1번 노드와 연결된 노드들
  [2, 3, 8],          # 2번 노드와 연결된 노드들
  [1, 7],             # 3번 노드와 연결된 노드들
  [1, 4, 5],          # 4번 노드와 연결된 노드들
  [3, 5],             # 5번 노드와 연결된 노드들
  [3, 4],             # 6번 노드와 연결된 노드들
  [7],                # 7번 노드와 연결된 노드들
  [2, 6, 8],          # 8번 노드와 연결된 노드들
  [1, 7]              # 9번 노드와 연결된 노드들
]

def DFS(graph, visited, start):
  # 현재 노드를 방문 처리
  visited[start] = True
  print(start, end = ' ')

  for i in graph[start]:
    if not visited[i]:
      DFS(graph, visited, i) // 재귀함수!!

# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
DFS(graph, visited, 1)

---

🔎BFS (Breadth First Search)

너비 우선 탐색으로, deque를 사용하여 구현

 

구현 방법

1. graph를 배열의 형태로 완성한다.cf) 양방향인 경우, 양쪽에 적어야한다.
   → 각 index에 해당 index번째 노드와 연결된 간선의 번호를 적는다.
2. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.
3. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
4. 2번이 불가능 할때까지 반복한다.

from collections import deque

# BFS
def BFS(graph, visited, start):
  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

# 노드는 9개지만, index 0번 노드는 사용하지 않는다.
visited =[False] * 10

# 각 노드가 연결된  정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
  [],                 # 빈 자리
  [],                 # 1번 노드와 연결된 노드들
  [2, 3, 8],          # 2번 노드와 연결된 노드들
  [1, 7],             # 3번 노드와 연결된 노드들
  [1, 4, 5],          # 4번 노드와 연결된 노드들
  [3, 5],             # 5번 노드와 연결된 노드들
  [3, 4],             # 6번 노드와 연결된 노드들
  [7],                # 7번 노드와 연결된 노드들
  [2, 6, 8],          # 8번 노드와 연결된 노드들
  [1, 7]              # 9번 노드와 연결된 노드들
]

BFS(graph, visited, 1)

✏️팁

• 둘다 O(NlogN)의 시간 복잡도를 지닌다.
• True / False를 적극 활용하기

visited =[False] * (N+1)

• ⭐노드가 1부터 시작하는 경우, graph와 visited도 1부터 시작하기 → 헷갈림 방지
• DFS의 재귀가 이미 visited를 모두 방문했음에도 실행하고 있을 때를 대비하여, 해 호출마다 check_end 함수를 넣을 수 있음.
• 일반적으로, BFS가 DFS보다 빠름.