DFS & BFS

그래프 탐색 알고리즘: DFS/BFS
- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

* DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이다! 

 

- 스택 자료구조

 

stack = []
stack.append(5)
stack.pop()

# 최상단 원소부터 출력
print(stack[::-1])

# 최하단 원소부터 출력
print(stack)

 

- 큐 자료구조

 

from collections import deque

queue=deque()
queue.append(5)
queue.append(2)
queue.popleft()

print(queue)
queue.reverse()
print(queue)

 

- 재귀 함수

자기 자신을 다시 호출하는 함수, 종료 조건을 무조건 포함해야한다.

 

def recursive_function(i):
	if i==100:
    	return 1

	recursive_function(i+1)
    
recursive_fuction(1)

 

*팩토리얼 구현해보기

def factorial(i):
    
    if i<=0:
        return 1
  
    return i*factorial(i-1)

print(factorial(4))

 

- 유클리드 호제법

두 개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘

: 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다.
: 이때 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다.

 

ex. A가 192, B가 162라고 하자. 

-> A와 B의 최대 공약수는 B(162) A를 B로 나눈 나머지(30)의 최대 공약수와 같다. 

-> 나머지(30)과 162를 30으로 나눈(12)의 최대 공약수와 같다.
-> 12와 6의 최대 공약수와 같다.

 

결론: 최대 공약수는 6이다.

 

def gcd(a,b):
	if a%b == 0:
    	return b
    else:
    	return gcd(b,a%b)
        
print(gcd(192,162))

 

-> 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.

-> 재귀 함수가 반복문보다 유리한 경우도, 불리한 경우도 있다.

-> 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓이므로 스택을 사용해야할 때 스택 라이브러리 대신 재귀함수를 이용하는 경우도 많다. 

 

DFS란? (depth first search)

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

- 동작 과정
   1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

   2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가         없으면 스택에서 최상단 노드를 꺼낸다.

   3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복한다.

 

#그래프 표현 (0번 노드에 대한 내용은 비운다.)
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]

#방문된 정보 표현
visited = [False] * 9
dfs(graph, 1, visited)

def dfs(graph, v, visited):
	visited[v]=True
    print(v,end='')
    #인접한 노드 중 방문하지 않은 것이 있다면 
    for i in graph[v]:
    	if not visited[i]:
        	# 그 i를 기준으로 다시 탐색 시작
        	dfs(graph, i, visitied)

 

BFS란? (breadth first search)

- BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.

- 큐 자료구조를 이용한다.

    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다. (dfs와 다르게 한번      에 삽입한다.)

    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

: 간선의 비용이 같다면 최단 거리를 찾을 수 있다. 

 

from collections import deque
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]

visited = [False] * 9
bfs(graph,1,visited)

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

 

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

 

-> 아이디어: DFS 이용(0을 방문처리를 하고, 방문 처리가 되는 경우만 count하자. )

1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.

2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 진행하는 과정을 반복하면, 연결된 모든 지점을 방문할 수 있다.
3. 모든 노드에 대하여 1~2번의 과정을 반복하며, 방문하지 않은 지점의 수를 카운트한다.

 

n,m =map(int, input().split())
graph=[]
for i in range(n):
	graph.append(list(map(int, input())))
    
result=0
for i in range(n):
	for j in range(m):
    	if dfs(i,j)== True:
        	result+=1
print(result)


def dfs(x,y):
	if x<=-1 or x>=n or y<=-1 or y>=m :
    	return False
       
    if graph[x][y]==0:
    	graph[x][y]=1
		dfs(x-1,y)
        dfs(x,y-1)
		dfs(x+1,y)
		dfs(x,y+1)
		return True
	return False

 

문제) 미로 탈출
동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혔습니다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야합니다.
동빈이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있습니다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있습니다. 미로는 반드시 탈출할 수 있는 형태로 제시됩니다.

이떄 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하세요.

 

-> 아이디어: BFS (간선의 크기가 같고 최단 거리를 구할 때 사용한다.)

 

from collections import deque
def bfs(x,y):
	queue=deque()
    queue.append((x,y))
    
    while queue:
    	x,y=queue.popleft()
        
        for i in range(4):
        	nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or nx>=n or ny<0 or ny>=m:
            	continue
            if graph[nx][ny]==0:
            	continue
                
            if graph[nx][ny]==1:
            	graph[nx][ny]=graph[x][y]+1
                queue.append((nx,ny))
	return graph[n-1][m-1]

n,m=map(int, input().split())
graph=[]

for i in range(n):
	graph.append(list(map(int,input())))
    
dx[-1,1,0,0]
dy=[0,0,-1,1]
print(bfs(0,0))

 

참고) 이것이 취업을 위한 코딩 테스트다 with 파이썬