[Daira i Noor] Python Algorithm (2) - Brute Force Search

오늘은 파이썬을 통해 완전 탐색을 하는 방법에 대해 알아본다.

완전 탐색의 방법으로 단순한 brute force와, 순열의 활용, BFS/DFSk에 대해서 알아본다.

 

Brute Force

for문과 if문을 활용하여 모든 가능한 경우를 검사하는 방법이다. 코테에서 brute force는 사실 많이 나오는 풀이방법은 아니지만, 풀이 과정에서 간단하게 활용할 수 있다.

 

 

순열의 활용

파이썬으로 순열을 사용하는 방법은 아래의 포스팅에 소개되어있다.

https://he-kate1130.tistory.com/70

[python] "코테"를 위한 기초 파이썬 (5) - 순열, 조합, 중복 순열, 중복 조합

 

간단하게, itertools의 permutation을 이용한다.

from itertools import permutations

my_List = [1,2,3,4,5]
for _,elements in enumerate(permutations(my_List,2)):
    print(elements)
    
#(1, 2)
#(1, 3)
#  ...
#(5, 3)
#(5, 4)

 

중학생때 배우듯이, 순열의 경우의 수는 N!이므로, 완전탐색에서 순열을 사용하는것이 적절한지 잘 판단하여 사용하자.

 

 

DFS

깊이 우선탐색은 기본적으로 stack을 이용

DFS함수를 재귀적으로 호출하여 구현한다.

from collections import deque

def DFS(now): # now: 현재 방문한 노드
	visited[now] = True #현재 노드 방문 표시
    stack.append(map(int,graph[now]))  #현재 노드의 모든 자식 노드들을 스택 추가
    
    while(stack):
    	nxt = stack.pop()
    	if not visited[nxt]: DFS(nxt) # 방문하지 않았다면 방문대상

 

 

BFS

너비 우선 탐색은 기본적으로 queue를 이용

BFS함수 내에서 반복문을 통해 구현

from collections import deque

def BFS(start): # now: 현재 방문한 노드
	visited[start] = True #방문 완료
	queue.append(map(int,graph[start]) # 모든 자식 노드를 큐에 추가
    
    while queue: #방문 대상 존재
    	now = queue.popleft()
        if not visited[now]: #아직 방문하지 않은 곳일때
        	visited[now] = True #방문 완료
        	queue.append(map(int,graph[now]) # 모든 자식 노드를 큐에 추가