TIL : DFS & BFS, 완전탐색 활용 알고리즘 문제

DFS (Depth First Search)

---

• 위에서 아래로 찾는 방식. 이때 좌우 방향은 중요치 않다.
• 특정 노드가 방문한 적 없는 노드라면 계속 검색하고, 이미 방문한 노드라면 무시하거나 따로 저장하는 방식으로 구현한다.

1. 재귀로 구현한 DFS

visited = set()

def dfs(visited, graph, node) :
    if node not in visited :
        print (node)
        visited.add(node)
        for neighbour in graph[node] :
            dfs(visited, graph, neighbour)

dfs(visited, graph, 'A')

def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐 
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited

• 재귀는 대개 for문으로 바꿀 수 있다. 복잡할 뿐이다.

1. 스택과 리스트를 활용한 구현

def dfs(v, visited=[]):
    visited.append(v)
    for w in graph[v]:
        if not w in visited:
            visited = recursive_dfs(w, visited)
    return visited

def dfs2(graph, start_node):
    need_visited, visited = list(), list()
    need_visited.append(start_node)
    
    while need_visited:
        node = need_visited.pop()

        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
            
    return visited

• need_visited에서 추가된 Node들 중에 가장 끝에 있는 것을 뽑아서 검색하는 방식
• 단 list에서 pop을 활용하면 성능이 떨어진다는 단점이 존재한다.

1. Deque를 활용한 DFS 구현

def dfs2(graph, start_node):
    from collections import deque
    visited = []
    need_visited = deque()
    need_visited.append(start_node)
    
    while need_visited:
        node = need_visited.pop()
 
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
                
    return visited

BFS (Breadth First Search)

---

• 수평 방향으로 노드를 탐색하는 방식.
• DFS와 마찬가지로 방문한 적 있는 노드와 없는 노드를 구분해 구현한다.

1. 스택을 활용한 구현

visited = []
queue = []

def bfs(visited, graph, node) :
    visited.append(node)
    queue.append(node)
    
    while queue :
        s = queue.pop(0)
        print (s)
        
        for neighborhood in graph[s] :
            if neighborhood not in visited :
                visited.append(neighborhood)
                queue.append(neighborhood)

bfs(visited, graph ,'A')

def bfs2(start_v):
    visited = []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.append(v)
            for w in graph[v]:
                stack.append(w)

return visited

1. 리스트 자료형을 활용한 BFS 구현

def bfs(graph, start_node):
    **need_visited**, visited = [], []
    need_visited.append(start_node)
    
    
    while need_visited:
        node = need_visited[0]
        del need_visited[0]
        
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
    return visited- 

• DFS와 BFS의 가장 큰 차이점은 While문 다음에 어떤 자료를 우선적으로 추출하느냐이다.
• DFS는 리스트의 가장 끝에 있는 데이터를 기준으로 추출하지만, BFS는 리스트의 가장 처음에 있는 인자를 받는다. 그래서 need_visited[0]라는 코드가 존재하는 것이다.

•  

프로그래머스 - 최소 직사각형 (완전 탐색 유형)

---

• 생각 쪼개보기
  1. 일단 어쩔 수 없이 모든 명함 크기에 대해 아래 연산은 다 해야 한다. ⇒ 완전탐색 유형
  2. 명함은 돌려서 넣을 수 있다.
  3. 가로, 세로 중 긴 값은 무조건 가로로, 짧은 값은 무조건 세로로 간주한다.
  4. 가장 큰 가로 X 세로가 가장 큰 값이 정답
• 내 풀이

def solution(sizes):
    for size in sizes :
        if size[1] > size[0] :
            size[0], size[1] = size[1], size[0]
    width = [x[0] for x in sizes]
    height = [x[1] for x in sizes]
    return max(width)*max(height)

• 다른 풀이

def solution(sizes) :
    width = 0
    height = 0
    
    for i in range(len(sizes)) :
        sizes[i].sort()
        width = max(width, sizes[i][0])
        height = max(height, sizes[i][1])
    
    answer = width * height
    return answer

프로그래머스 - 소수 찾기 (순열 유형의 완전 탐색 유형)

---

• 소수 판별의 부담이 없다면(소수 판별 함수 암기해두면 좋음) 사실상 문자열 numbers를 어떻게 조합할지의 문제나 다름 없다.
• 생각 쪼개보기
  1. 흩어진 종이 조각을 바탕으로 완전 탐색
  2. → 순서가 중요한 경우의 수를 찾아야겠네 ←순열 (순열이 사용된 완전 탐색)
  3. numbers 문자열의 각 숫자 떼어내기
  4. 분리된 숫자들의 순열 만들기
  5. 숫자들을 하나의 숫자로 만들기
  6. 각 숫자에 대하여 소수인지 판별하기
• 내 풀이

from itertools import permutations

def is_prime_number(num):
    if num==0 or num==1:
        return False
    else:
        for n in range(2, (num//2)+1):
            if num % n == 0:
                return False        
        return True
    
def solution(numbers) :
    # 종이에 적힌 숫자 떼어내기
    number_list = list(map(int, numbers))
    
    # 한자릿수 조합부터 가장 큰 수와 동일한 자릿수까지 모든 조합 구하기
    permute_list = []
    for i in range(1, len(number_list)+1) :
        permute = list(permutations(number_list, i))
        permute_list += permute
        
    # 조합 중 소수에 해당하는 조합만 골라내기
    permute_numbers = []
    for pl in permute_list :
        permute_number = ""
        for p in pl :
            permute_number += str(p)
        permute_numbers.append(int(permute_number))
    
    # 중복값 없애고 해당 set 안 요소의 개수 반환
    prime_set = []
    for i in permute_numbers :
        if is_prime_number(i) :
            prime_set.append(i)
    
    return len(set(prime_set))

• 다른 풀이

from itertools import permutations

def is_prime_number(num):
    if num==0 or num==1:
        return False
    else:
        for n in range(2, (num//2)+1):
            if num % n == 0:
                return False        
        return True

def solution2(numbers) :
    answer = []
    
    # numbers 분리하기
    nums = [n for n in numbers]
    
    # 분리된 숫자들의 순열 만들기
    per = []
    for i in range(1, len(numbers)+1) :
        per += list(permutations(nums, i))
    
    # 순열로 만들어진 수를 하나의 수로 만들기
    new_nums = [int(("").join(p)) for p in per]
    
    # 모든 ㅑnt형 숫자에 대해 소수인지 판별
    for n in new_nums :
        # 소수일 경우 answer 배열에 추가
        if is_prime_number(n) :
            answer.append(n)
    
    return len(set(answer))