DFS/BFS

대표적인 탐색 알고리즘
-> 스택, 큐, 재귀 함수 개념으로 해결

• 스택 : 선입후출 구조
  .append() - 삽입
  .pop() - 마지막 원소 삭제
  print(stack) -최하단 원소부터 출력
  print(stack[::-1]) - 최상단 원소부터 출력

• 큐 : 선입선출 구조, deque 라이브러리 사용
  .append() - 삽입
  .popleft() - 첫 원소 삭제
  .reverse() - 역순으로 바꾸기

• 재귀함수
  종료조건 꼭 명시하기 ( 함수 무한호출 방지 )
  점화식과 형태 비슷

그래프 표현 방식

• 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  연결되어 있지 않은 노드끼리는 무한의 비용 ( 예: 999999 )으로 표시
  노드의 개수가 적을 때 사용 !

INF = 9999

graph = [
	[0,7,5],
    [7,0,INF],
    [5,INF,0]
]

print(graph)

예: 노드 1과 7이 연결되어 있는 상황 확인 -> graph[1][7] 값이 INF인지 정수인지 확인 !

• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
  모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장

graph = [[] for _ in range(3)]  # 행의 개수는 3

graph[0].append((1,7))  # (노드, 거리)
graph[0].append(2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

DFS

• 탐색 시작 노드부터 인접 노드들을 차례로! 모두! 스택에 방문처리 해주는 것이 중요
• 재귀 함수 사용

def dfs(graph,v,visited):  # graph는 인접 행렬 형태로 저장
	visited[v] = True  # 현재 노드를 방문 처리
    print(v, end=' ')
	# 현재 노드와 연결된 노드를 재귀적으로 방문
    for i in graph[v]:
    	if visited[i] != True:
        	dfs(graph,i,visited)
            
visited = [False] * (행의 개수 + 1)

BFS

• 가까운 노드부터 큐에 넣으면서 탐색하는 방식
• 큐에서 노드를 꺼내서 인접 노드 중에 방문하지 않은 노드를 모두 큐에 삽입 -> 방문 처리

from collections import deque

def bfs(graph,start,visited):
	queue = deque([start])
    # 큐가 빌 때까지 실행
    while queue:
    	v = queue.popleft() # 중간에 while 조건이 만족되더라도 while문 안에 들어온 이상, 끝까지 실행하고 탈출 
    	for i in graph[v]:
        	if visited[i] != True:
            	visited[i] = True
            	queue.append(i)
            
visited = [False] * (행의 개수 + 1)