[Python] 알고리즘의 종류, 종류별 예제 _ DFS/BFS (3/7)

자료구조 기초

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.

자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조

삽입(Push) : 데이터를 삽입한다.

삭제(PoP) : 데이터를 삭제한다.

*스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야함.

오버플로(Overflow)는 특정 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생.

즉, 저장공간을 벗어나 데이터가 넘쳐 흐를 때 발생

언더플로(Underflow)는 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로 발생

스택(Stack)

스택은 박스쌓기와 같아서 먼저 아래에 쌓았다면 이는 마지막에 나감.

선입후출, 후입선출

stack = []
stack.append(0) #삽입
stack.append(1) #삽입
stack.append(2) #삽입
stack.append(3) #삽입
stack.pop() #삭제
stack.append(5) #삽입
stack.append(6) #삽입
stack.append(7) #삽입
stack #[0,1,2,5,6,7]
stack[::-1] #[7,6,5,2,1,0]

큐(Queue)

큐는 대기줄에 비유할 수 있으며 먼저온사람이 먼저 들어가는 공정한 자료구조

선입선출

from collections import deque
queue = deque()
queue.append(5) #삽입
queue.append(2) #삽입
queue.append(3) #삽입
queue.append(7) #삽입
queue.popleft() #삭제
queue.append(1) #삽입
queue.append(4) #삽입
queue.popleft() #삭제

queue #deque([3,7,1,4])
queue.reverse()
queue #deque([4,1,7,3])

#deque를 이용해야 시간복잡도가 낮아짐(리스트 ㄴㄴ)

재귀함수

자기자신을 다시 호출하는 함수

팩토리얼을 계산하는 재귀함수 예제

#반복적로 구현한 n!
def factorial_iterative(n):
	result = 1
	for i in range(1, n + 1):
		result *= i
	return result
		
#재귀적으로 구현한 n!
def factorial_recursive(n):
	if i <= 1:
		return 1
	return n * factorial_recursive(n - 1)
	
#최대공약수 구하기
def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcb(b, a%b)

DFS (Depth - Frist Search)

동작과정

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

def dfs(graph, v, visited):
	visited[v] = True
	print(v, end = ' ')
	for i in graph[v]:
		if not visited[i]:
			dfs(graph, i, visited)

BFS(Breadth-First Search)

동작과정

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

from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		print(v)
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

#간선간의 비용을 무시하고 최단거리를 찾을때 효과적

예제 p.149

음료수 얼려먹기(DFS)

n, m = map(int, input().split())
graph = []
for i in range(0, n):
    graph.append(list(map(int, input())))
	
visited = [[0] * m for _ in range(n)]

def dfs(graph, x, y, visited):
    if x <= -1 or y <= -1 or x >= m or y >= n:
        return False
    if graph[y][x] == 0 and visited[y][x] == 0:
        visited[y][x] = 1
        dfs(graph, x+1, y, visited)
        dfs(graph, x-1, y, visited)
        dfs(graph, x, y+1, visited)
        dfs(graph, x, y-1, visited)
        return True
    return False
		
cnt = 0
for i in range(0, m):
	for j in range(0, n):
		if dfs(graph, i, j, visited):
			cnt += 1
print(cnt)

예제 P.152

미로 탈출

from collections import deque
from pprint import pprint

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x, y):
    q = deque()
    q.append((x,y))

    while(q):
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            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
                q.append((nx, ny))
    return graph[n-1][m-1]

print(bfs(0,0))
pprint(graph)

n, m = map(int, input().split())
graph = []
for i in range(0, n):
	graph.append(list(map(int, input())))
	
visited = [0] * m for _ in range(n)

def dfs(graph, x, y. visited):
	if x <= -1 or y <= -1 or x >= m or y >= n:
		return False
	if graph[y][x] == 0 and visited[y][x] == 0
		visited[y][x] = 1
		dfs(graph, x, y, visited)
		dfs(graph, x, y, visited)
		dfs(graph, x, y, visited)
		dfs(graph, x, y, visited)
		return True
	return False
		
cnt += 0
for i in range(0, n):
	for j in range(0, m):
		if dfs(graph, x, y, visited):
			cnt += 1