코딩테스트 공부 day3 [DFS/BFS]

본 자료는 '동빈나' 유튜브를 참고했습니다. 

https://www.youtube.com/watch?v=7C9RgOcvkvo 

1.스택 자료구조

- 먼저 들어 온 데이터가 나중에 나가는 형식 (선입후출)의 자료 구조

- 입구와 출구가 동일한 형태 

 

stack = [] 

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3) 
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

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

실행결과 
[1,3,2,5]
[5,2,3,1]

 

2. 큐 자료구조 

- 먼저 들어 온 데이터가 먼저 나가는 형식 (선입선출) 자료 구조 

- 입구와 출구가 모두 뚫려 있는 터널과 같은 형태 (대기열 형태)

from collections import deque 

# 큐 구현을 위해 deque 라이브러리 사용 
queue = deque() 

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3) 
queue.append(7)
queue.pop()
queue.append(1)
queue.append(4)
queue.pop()

print(queue) #먼저 들어온 순서대로 출력 
queue.reverse() #역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력 


실행결과
deque([3,7,1,4])
deque([4,1,7,3])

3. 재귀함수 (recursive_function)

: 자기 자신을 다시 호출하는 함수를 의미 

 

ex ) 팩토리얼 구현 예제 

#반복적으로 구현한 n! 
def factorial_iterative(n) :
	result = 1 
    for i in range(1 , n+1) :
    	result  = result * i 
    return result 
    
    
#재귀적으로 구현한 n! 
def factorial_recursive(n) :
	if n <= 1 : #n이 1 이하인 경우를 반환 
    	return 1 
    return n * factorial_recursive(n-1)

 

ex ) 최대공약수 계산 (유클리드 호제법) 예제 

유클리드 호제법 

 

- 두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 합니다. 

- 이때 A와 B의 최대공약수는 B와R의 최대공약수와 같습니다. 

 

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

인접행렬의 DFS ,BFS  

6 6 
0 1 1 1 1 1
0 1 0 0 0 1 
0 1 0 1 0 1
0 1 0 1 0 0
0 0 0 1 1 0
1 1 1 1 1 0

n,m = map(int,input().split()) 
arr = []
for i in range(n) :
	row = list(map,int(input().split()))
    arr.append(row) 
print(arr)

 

DFS 함수

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DFS(Depth - First Search) 

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

 

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

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

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) 
            
            
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 표현 
visited = [False] * 9 

#정의된 DFS 함수 호출
dfs(graph , 1 , visited)

BFS(Breadth - First Search) 

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

- BFS는 큐 자료구조 이용

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리한다.

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 

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

 

from collections import deque

def bfs(graph , start , visited) :
	#큐 구현을 위해 deque 라이브러리 사용  
    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,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

#각 노드가 방문된 정보를 표현 
visited = [False] * 9 

#정의된 BFS 함수 호출
bfs(graph , 1 , visited)

<문제> 음료수 얼려먹기 

Q. NXM 크기의 얼음 틀이 있습니다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시됩니다. 구멍이 뚫려있는 부분은 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주합니다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하세요. 다음의 얼음 틀 예시에서는 아이스크림이 총 3개가 생성됩니다. 

 

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 , m = map(int,input().split())
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)

<문제> 미로 탈출 

Q. 동빈이는 NXM 크기의 직사각형 형태의 미로에 갇혔습니다. 미로는 여러 마리의 괴물이 있어 이를 피해 탈출해야 합니다. 동빈이의 위치는 (1,1)이며 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있습니다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있습니다. 미로는 반드시 탈출할 수 있는 형태로 제시됩니다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하세요. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산합니다. 

 

 

... dfs/bfs는 여전히 어렵네요. 다시 공부해서 완전히 이해했을때 다시 포스팅 하겠습니다.