Week-2: 검색 문제

DSA-알고리즘 스터디

Jan 12, 2022

검색 문제
DNA 검색
미로 찾기
선교사와 식인종
- 개요: 문제 나타내기
- 제네릭 프로그래밍의 힘
연습문제

검색 문제

세 개의 문제에 사용되는 알고리즘은 제네릭 프로그래밍 기법을 통해 일반화한 뒤 광범위한 문제에 적용할 수 있다.

본 문서에서 제네릭 프로그래밍을 사용한 챕터는 💾를, 연습문제를 푼 챕터는 📝을 표시했다.

시작하기 앞서 다음 모듈을 import해 타입 힌트와 힙 사용을 준비한다.

# import
from __future__ import annotations
from typing import TypeVar, Iterable, Sequence, Generic, List, Callable, Set, Deque, Dict, Any, Optional
from typing_extensions import Protocol
from heapq import heappush, heappop

DNA 검색

# import
from enum import IntEnum
from typing import Tuple, List

개요: 구조 표현하기

뉴클레오타이드(Nucleotide)

A, C, G, T 중 하나로 표현한다.

Nucleotide:IntEnum = IntEnum('Nucleotide', ('A', 'C', 'G', 'T'))

Note

Enum 모듈을 사용해 파이썬에서도 열거 타입을 사용할 수 있다. 후술할 이진 검색 알고리즘에서 뉴클레오타이드에 대한 비교가 발생하므로 비교 연산자를 지원하는 IntEnum 타입을 사용한다.

코돈(Codon)

세 개의 뉴클레오타이드로 구성된다.

Codon = Tuple[Nucleotide, Nucleotide, Nucleotide]

🛴 https://dodona.ugent.be/en/activities/1424446086/

유전자(Gene)

다수의 코돈으로 구성된다.

Gene = List[Codon]

Note

타입 앨리어스(Type alias)를 사용해 긴 타입명 대신 짧은 별칭을 지정함으로써, 타입 힌트가 길어질 때 발생하는 문제를 해결할 수 있다. 예를 들어 Codon은 3개의 Nucleotide로 구성된 Tuple 타입이므로 Tuple[Nucleotide, Nucleotide, Nucleotide]로 표현할 수 있다. 하지만 긴 타입명은 변수 선언 과정이 번거로울 뿐 아니라 코드의 직관성과 간결성을 해치므로 Codon으로 짧게 표현한다.

검색 작업을 시행하기 앞서 주어진 뉴클레오타이드로 구성된 문자열을 3글자씩 끊어서 유전자 리스트를 생성한다.

def string_to_gene(s:str) -> Gene:
    gene:Gene = []
    for i in range(0, len(s), 3):
        if (i + 2) >= len(s):
            return gene
        codon:Codon = (Nucleotide[s[i]]), Nucleotide[s[i+1]], Nucleotide[s[i+2]]
        gene.append(codon)
    return gene

gene_str:str = "ACGTGGCTCTCTAACGTACGTACGTACGGGGTTTATATATACCCTAGGACTCCCTTT"
my_gene:Gene = string_to_gene(gene_str)

선형 검색

유전자 리스트가 특정 코돈(Key)를 포함하고 있는지 확인하는 과정을 검색이라고 하며, 두 가지 방법으로 검색 알고리즘을 구현할 수 있다.

선형 검색(또는 순차 검색)은 유전자 리스트의 모든 코돈에 대해 Key와 비교하는 방식으로 이루어진다. 만약 값이 같다면 검색 성공이므로 True를 리턴하고, 값이 다르다면 다음 코돈으로 넘어간다. Key와 같은 코돈이 하나도 존재하지 않는다면 검색 실패이므로 False를 리턴한다.

선형 검색은 리스트 내 항목의 개수가 N일 때 최대 N번의 비교가 이루어지며, 따라서 O(N)의 시간복잡도를 갖는다.

def linear_contains(gene:Gene, key_codon:Codon) -> bool:
    for codon in gene:
        if codon == key_codon:
            return True
    return False

💾 선형 검색의 일반화

방금 작성한 알고리즘은 다른 종류의 검색 알고리즘에는 사용할 수 없다. 따라서 일반화 과정을 거치는 과정이 필요하다.

기존 알고리즘	일반화 알고리즘
검색할 값: `Codon` 3개의 Nucleotide 타입으로 구성된 Tuple 타입	검색할 값 `T` 사용자 정의 타입으로, 어떤 타입도 상관없음
검색의 범위: `Gene` Codon 타입으로 구성된 List 타입	검색의 범위 `Iterable[T]` T로 구성된 Iterable(str, list, tuple, dict, set 등) 타입

TypeVar을 사용해 사용자 정의 타입 T를 표현한다.

T = TypeVar('T')

이제 Codon과 Gene을 각각 T와 Iterable[T]로 치환해 선형 검색 알고리즘을 일반화한다.

def linear_contains(iterable:Iterable[T], key:T) -> bool:
    for item in iterable:
        if item == key:
            return True
    return False

이진 검색

이진 검색은 유전자 리스트의 임의의 코돈과 Key의 대소 관계를 비교한 뒤, 탐색 범위를 좁히는 방식으로 이루어진다. 임의의 값이 찾고자 하는 값보다 크다면 더 작은 범위에서 임의의 값을 재지정하며, 반대로 임의의 값이 찾고자 하는 값보다 작다면 더 큰 범위에서 임의의 값을 재지정한다. 만약 두 값이 같다면 검색 성공이므로 True를 리턴하고, 탐색 범위를 더 이상 좁히지 못한다면 검색 실패이므로 False를 리턴한다.

단, 위 방법이 성립하기 위해서는 유전자 리스트가 정렬되어 있어야 한다.

이진 검색은 리스트 내 항목의 개수가 N일 때 최대 logN번의 비교가 이루어지며, 따라서 O(logN)의 시간복잡도를 갖는다.

def binary_contains(gene:Gene, key_codon:Codon) -> bool:
    low:int = 0
    high:int = len(gene) - 1
    while low <= high:
        mid:int = (low + high) // 2
        if gene[mid] < key_codon:
            low = mid + 1
        elif gene[mid] > key_codon:
            high = mid - 1
        else:
            return True
    return False

💾 이진 검색의 일반화

선형 검색 알고리즘과 마찬가지로 이진 검색 알고리즘 역시 일반화할 수 있다.

기존 알고리즘	일반화 알고리즘
검색할 값: `Codon` 3개의 Nucleotide 타입으로 구성된 Tuple 타입	검색할 값 `C` 사용자 정의 타입으로, 비교 연산을 지원해야 함
검색의 범위: `Gene` Codon 타입으로 구성된 List 타입	검색의 범위 `Sequence[C]` C로 구성된 Sequence(str, list, tuple) 타입

이진 검색은 선형 검색과 다르게 비교 연산이 이루어지므로 이를 지원하는 새로운 사용자 정의 타입을 만들어야 한다. 또한 검색의 범위가 정렬되어 있어야 하므로 Iterable 대신 Sequence를 사용해야 한다.

Note

Sequence 타입은 Iterable 타입 중에서도 순서가 있는 타입을 의미한다. 즉, 인덱싱과 슬라이싱을 지원해야 한다. 정렬 역시 항목을 순서대로 재배열하는 것을 의미하므로, 오직 Sequence 타입에서만 지원한다.

TypeVar을 사용해 비교 연산을 지원하는 사용자 정의 타입 C를 표현한다.

C = TypeVar("C", bound="Comparable")

비교 연산자를 구현하는 Comparable 클래스를 구현한다.

class Comparable(Protocol):
    def __eq__(self, other:Any) -> bool:
        ...
    def __lt__(self:C, other:C) -> bool:
        ...
    def __gt__(self:C, other:C) -> bool:
        return (not self < other) and self != other
    def __le__(self:C, other:C) -> bool:
        return self < other or self == other
    def __ge__(self:C, other:C) -> bool:
        return not self < other

이제 Codon과 Gene을 각각 C와 Sequence[C]로 치환해 선형 검색 알고리즘을 일반화한다.

def binary_contains(sequence:Sequence[C], key:C) -> bool:
    low:int = 0
    high:int = len(sequence) - 1
    while low <= high:
        mid:int = (low + high) // 2
        if sequence[mid] < key:
            low = mid + 1
        elif sequence[mid] > key:
            high= mid - 1
        else:
            return True
        return False

미로 찾기

# import
from enum import Enum
from typing import List, NamedTuple, Callable, Optional
import random
from math import sqrt
from generic_search import Node, node_to_path, dfs, bfs, astar

개요: 미로 생성하기

2차원 격자의 미로를 생성한 뒤, 이를 바탕으로 미로 찾기 알고리즘을 작성한다.

Cell 클래스에서는 미로에서의 각 칸의 상태를 표시한다.

class Cell(str, Enum):
    EMPTY   = " "
    BLOCKED = "X"
    START   = "S"
    GOAL    = "G"
    PATH    = "*"

MazeLocation 클래스에서는 네임드튜플(NamedTuple)을 사용해 미로에서 각 칸의 위치를 행과 열로 나타낸다.

class MazeLocation(NamedTuple):
    row:int
    column:int

Note

네임드튜플(NamedTuple)에서는 사용자가 항목에 이름을 붙여 사용할 수 있다. 클래스처럼 선언하고 접근하지만 클래스에 비해 적은 메모리 공간을 사용한다. 기존 튜플의 성질도 가지고 있기에 항목은 불변하며 인덱스 방식을 사용해 항목에 접근할 수도 있다.

Maze 클래스에서는 미로를 생성한다.

class Maze:
    def __init__(self, rows:int = 10, columns:int = 10,
                sparseness:float = 0.2,
                start:MazeLocation = MazeLocation(0, 0),
                goal:MazeLocation = MazeLocation(9, 9)) -> None:
        self._rows:int = rows
        self._columns:int = columns
        self.start:MazeLocation = start
        self.goal:MazeLocation = goal
        self._grid:List[List[Cell]] = [[Cell.EMPTY for c in range(columns)] for r in range(rows)]
        self._randomly_fill(rows, columns, sparseness)
        self._grid[start.row][start.column] = Cell.START
        self._grid[goal.row][goal.column] = Cell.GOAL
        
    def _randomly_fill(self, rows:int, columns:int, sparseness:float):
        for row in range(rows):
            for column in range(columns):
                if random.uniform(0, 1.0) < sparseness:
                    self._grid[row][column] = Cell.BLOCKED

    def __repr__(self) -> str:
        output:str = ""
        for row in self._grid:
            output += " ".join([c.value for c in row]) + "\n"
        return output

    def goal_test(self, ml:MazeLocation) -> bool:
        return ml == self.goal

    def successors(self, ml:MazeLocation) -> List[MazeLocation]:
        locations:List[MazeLocation] = []
        if ml.row + 1    < self._rows    and self._grid[ml.row + 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row + 1, ml.column))
        if ml.row - 1    >= 0            and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row - 1, ml.column))
        if ml.column + 1 < self._columns and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column + 1))
        if ml.column - 1 >= 0            and self._grid[ml.row][ml.column - 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column - 1))
        return locations

    def mark(self, path:List[MazeLocation]):
        for maze_location in path:
            self._grid[maze_location.row][maze_location.column] = Cell.PATH
        self._grid[self.start.row][self.start.column] = Cell.START
        self._grid[self.goal.row][self.goal.column] = Cell.GOAL

    def clear(self, path:List[MazeLocation]):
        for maze_location in path:
            self._grid[maze_location.row][maze_location.column] = Cell.EMPTY
        self._grid[self.start.row][self.start.column] = Cell.START
        self._grid[self.goal.row][self.goal.column] = Cell.GOAL

__init__: 크기(rows, columns) 및 막힌 공간이 차지하는 비율(sparseness)을 바탕으로 미로를 생성한 뒤, 특정 칸에 시작 위치와 종료 위치를 표시한다.
_randomly_fill: 미로의 일정 부분을 무작위로 막힌 공간 Cell.BLOCKED으로 바꾼다. sparseness가 0.2면 약 20%의 공간이 막히게 된다.
__repr__: 미로를 출력한다.
goal_test: 말이 종료 위치에 도달했는지 확인한다.
successors: 해당 위치에서 말이 이동 가능한 위치를 리스트로 반환한다. 미로의 가장자리에 위치하거나 상하좌우에 막힌 공간이 있다면 그만큼 경로는 제한된다.
mark: 말의 이동 경로를 Cell.PATH로 표시한다.
clear: 미로를 초기화한다. 모든 칸을 Cell.EMPTY로 바꾸면 된다.

미로가 잘 생성되었는지 확인한다.

if __name__ == "__main__":
    m:Maze = Maze()
    print(m)

S               X  

  X
    X     X       X

          X
X     X
      X       X

    X X X     X   G

💾 Node와 경로 출력

미로에서의 경로는 다음과 같이 표현할 수 있다.

미로의 시작 위치는 트리의 루트에 존재한다. 이후 successors 함수에 의해 갈 수 있는 노드가 최대 4개 표시된다. Node 클래스에 노드의 속성을 작성한다.

class Node(Generic[T]):
    def __init__(self, state:T, parent:Optional[Node], cost:float = 0.0, heuristic:float = 0.0):
        self.state:T = state
        self.parent:Optional[Node] = parent
        self.cost:float = cost
        self.heuristic:float = heuristic

    def __lt__(self, other:Node) -> bool:
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)

state와 parent는 미로의 경로 출력에 사용된다.
cost와 heuristic 및 lt 비교 메서드는 A* 알고리즘에서 노드가 가지는 비용을 계산하는 데 사용된다.

미로의 종료 위치 노드까지 이동하면 탐색 과정이 끝나며, parent(부모 노드)를 사용해 시작 위치 노드(루트)에서 종료 위치 노드까지의 경로를 리스트로 반환한다.

def node_to_path(node:Node[T]) -> List[T]:
    path:List[T] = [node.state]
    while node.parent is not None:
        node = node.parent
        path.append(node.state)
    path.reverse()
    return path

💾 깊이 우선 탐색(DFS)

막다른 지점에 도달하여 최종 결정 지점으로 돌아오기 전까지 가능한 깊게 탐색한다.

이를 구현하기 위한 자료구조로 스택(Stack)을 사용한다. 내부 구조로는 리스트를 사용한다.

class Stack(Generic[T]):
    def __init__(self) -> None:
        self._container:List[T] = []

    @property
    def empty(self) -> bool:
        return not self._container
    def push(self, item:T) -> None:
        self._container.append(item)
    def pop(self) -> T:
        return self._container.pop()
    def __repr__(self) -> str:
        return repr(self._container)

Note

@property 데코레이터를 사용해 메서드가 get 역할을 한다는 것을 명시할 수 있다.

이동할 때마다 노드를 push하며, 막다른 길에 이르면 pop한 뒤 새로운 자식 노드를 찾는다.

def dfs(initial:T, 
        goal_test:Callable[[T], bool], 
        successors:Callable[[T], List[T]]) -> Optional[Node[T]]:
    frontier:Stack[Node[T]] = Stack()
    frontier.push(Node(initial, None))
    explored:Set[T] = {initial}

    while not frontier.empty:
        current_node:Node[T] = frontier.pop()
        current_state:T = current_node.state
        if goal_test(current_state):
            return current_node
        for child in successors(current_state):
            if child in explored:
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))
    return None

실행

if __name__ == "__main__":
    solution1:Optional[Node[MazeLocation]] = dfs(m.start, m.goal_test, m.successors)
    if solution1 is None: print("깊이 우선 탐색으로 길을 찾을 수 없습니다!")
    else:
        path1:List[MazeLocation] = node_to_path(solution1)
        m.mark(path1)
        print(m)
        m.clear(path1)

S * * * * * * * X
              * *
  X   * * * *   *
    X *   X * * * X
  * * *
  *       X
X * * X
    * X       X
    * * * * * * * *
    X X X     X   G

PATH의 길이는 33개로, 막다른 길에 들어서야 경로를 바꾸는 식으로 이동하기 때문에 비효율적인 움직임을 보여준다.

💾 너비 우선 탐색(BFS)

탐색의 각 반복마다 출발 지점에서 한 계층의 노드를 가까운 지점부터 순차적으로 탐색함으로써 항상 최단 경로를 찾는다.

이를 구현하기 위한 자료구조로 큐(Queue)를 사용한다.

스택과 다르게 리스트는 큐의 내부 구조로 적합하지 않다. 제일 앞의 인덱스를 제거하는 dequeue 과정에서의 시간복잡도가 O(N)으로 비효율적이기 때문이다. 리스트 대신 덱(Deque)을 사용하면 O(1)의 상수 시간복잡도로 dequeue를 구현할 수 있다.

class Queue(Generic[T]):
    def __init__(self) -> None:
        self._container:Deque[T] = Deque()

    @property
    def empty(self) -> bool:
        return not self._container
    def push(self, item:T) -> None:
        self._container.append(item)
    def pop(self) -> T:
        return self._container.popleft()
    def __repr__(self) -> str:
        return repr(self._container)

스택 대신 큐를 사용한다는 점만 제외하면 dfs 알고리즘과 전체적인 구조가 같다.

def bfs(initial:T, 
        goal_test:Callable[[T], bool], 
        successors:Callable[[T], List[T]]) -> Optional[Node[T]]:
    frontier:Queue[Node[T]] = Queue()
    frontier.push(Node(initial, None))
    explored:Set[T] = {initial}

    while not frontier.empty:
        current_node:Node[T] = frontier.pop()
        current_state:T = current_node.state
        if goal_test(current_state):
            return current_node
        for child in successors(current_state):
            if child in explored:
                continue
            explored.add(child)
            frontier.push(Node(child, current_node))
    return None

실행

if __name__ == "__main__":
    solution2:Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successors)
    if solution2 is None: print("너비 우선 탐색으로 길을 찾을 수 없습니다!")
    else:
        path2:List[MazeLocation] = node_to_path(solution2)
        m.mark(path2)
        print(m)
        m.clear(path2)

S               X
*
* X
*   X     X       X
*
* *       X
X *   X
  *   X       X
  * * * * * * * *
    X X X     X * G

PATH의 개수는 17개로, 깊이 우선 탐색에 비해 개선된 움직임을 보여준다.

💾 A* 알고리즘

A* 알고리즘의 핵심 아이디어는 휴리스틱(heuristic)이며, 이는 종료 위치까지의 이동에 필요한 최소 비용을 의미한다.

이를 구현하기 위한 자료구조로 우선순위 큐(PriorityQueue)를 사용한다. 내부 구조로는 힙(heap)을 사용한다.

class PriorityQueue(Generic[T]):
    def __init__(self) -> None:
        self._container: List[T] = []
    
    @property
    def empty(self) -> bool:
        return not self._container
    def push(self, item:T) -> None:
        heappush(self._container, item)
    def pop(self) -> T:
        return heappop(self._container)
    def __repr__(self) -> str:
        return repr(self._container)

A* 알고리즘에서 각 노드 사이의 비용(cost)은 1로 고정된다. 이를 바탕으로 현재 위치에서 방문할 수 있는 노드가 가진 최저 비용을 계산한 뒤, 미로의 말은 가장 적은 휴리스틱을 가진 노드의 위치로 이동한다. 이미 방문한 노드 역시 비용이 계산되므로 일부 노드는 두 번 방문될 수 있다.

각 노드의 최소 비용을 value로 저장하기 위해 Set 대신 Dict를 사용한다.

def astar(initial:T, 
          goal_test:Callable[[T], bool], 
          successors:Callable[[T], List[T]], 
          heuristic:Callable[[T], float]) -> Optional[Node[T]]:
    frontier:PriorityQueue[Node[T]] = PriorityQueue()
    frontier.push(Node(initial, None, 0.0, heuristic(initial)))
    explored:Dict[T, float] = {initial: 0.0}

    while not frontier.empty:
        current_node:Node[T] = frontier.pop()
        current_state:T = current_node.state
        if goal_test(current_state):
            return current_node
        for child in successors(current_state):
            new_cost:float = current_node.cost + 1
            if child not in explored or explored[child] > new_cost:
                explored[child] = new_cost
                frontier.push(Node(child, current_node, new_cost, heuristic(child)))
    return None

Note

astar 알고리즘은 매개변수로 함수가 사용되며, 이에 대한 타입 힌트로 Callable을 사용한다. 파이썬에서는 1급 객체로서의 함수를 지원하기 때문에, 함수를 인자로 넘기거나 반환할 수 있다. 이처럼 순수 함수를 조합하는 프로그래밍 방식을 함수형 프로그래밍이라고 한다.

맨해튼 거리

최단거리를 구하는 가장 일반적인 방법은 피타고라스 정리를 활용한 방법이다. x좌표의 차이의 제곱과 y좌표의 차이의 제곱을 구한 뒤, 이들 합의 제곱근이 바로 두 지점 사이의 최단거리이다. 이렇게 구한 거리를 유클리드 거리라고 한다.

유클리드 거리를 구하는 함수는 다음과 같다.

# 유클리드 거리
def euclidean_distance(goal:MazeLocation) -> Callable[[MazeLocation], float]:
    def distance(ml:MazeLocation) -> float:
        xdist:int = ml.column - goal.column
        ydist:int = ml.row - goal.row
        return sqrt((xdist * xdist) + (ydist * ydist))
    return distance

하지만 격자로 이루어진 미로에서 대각선 이동은 존재하지 않으며, 오로지 상하좌우로만 이동만 가능하다. 이 때 두 지점 사이의 최단거리는 택시 기하학에서 거리를 구하는 방법인 맨해튼 거리로 표시할 수 있다.

맨해튼 거리를 구하는 함수는 다음과 같다.

# 맨해튼 거리
def manhattan_distance(goal:MazeLocation) -> Callable[[MazeLocation], float]:
    def distance(ml:MazeLocation) -> float:
        xdist:int = abs(ml.column - goal.column)
        ydist:int = abs(ml.row - goal.row)
        return (xdist + ydist)
    return distance

A* 알고리즘은 기존의 알고리즘과 다르게 추가로, 휴리스틱의 구현을 위한 맨해튼 거리 함수를 인수로 받는다.

실행

if __name__ == "__main__":
    distance:Callable[[MazeLocation], float] = manhattan_distance(m.goal)
    solution3:Optional[Node[MazeLocation]] = astar(m.start, m.goal_test, m.successors, distance)
    if solution3 is None: print("A* 알고리즘으로 길을 찾을 수 없습니다!")
    else:
        path3:List[MazeLocation] = node_to_path(solution3)
        m.mark(path3)
        print(m)

S               X
*
* X
*   X     X       X
* *
  * * * * X
X     X * * * * * *
      X       X   *
                  *
    X X X     X   G

PATH의 개수는 17개로, BFS 방식의 결과와 같지만 목표 지점까지 비용(거리) 계산을 바탕으로 이동하므로 대각선에 가까운 모양의 경로가 그려진다.

선교사와 식인종

# import
from __future__ import annotations
from typing import List, Optional
from generic_search import bfs, Node, node_to_path

개요: 문제 나타내기

선교사와 식인종 문제의 조건은 다음과 같다.

세 명의 선교사와 세명의 식인종이 강 서쪽에 있다.
이들은 두 명이 탈 수 있는 배를 갖고 있으며, 배를 타고 동쪽으로 이동해야 한다.
강 양쪽에 선교사보다 많은 식인종이 있다면 식인종은 선교사를 잡아먹는다.
강을 건널 때 배에는 적어도 한 명이 탑승해야 한다.

위 조건을 바탕으로 선교사와 식인종의 상태를 나타내는 클래스를 작성하고, 이를 통해 문제 해결을 시도할 수 있다.

MAX_NUM:int = 3

class MCState:
    def __init__(self, missionaries:int, cannibals:int, boat:bool) -> None:
        self.wm:int = missionaries
        self.wc:int = cannibals
        self.em:int = MAX_NUM - self.wm
        self.ec:int = MAX_NUM - self.wc
        self.boat:bool = boat

    def __repr__(self) -> str:
        return (f"서쪽 강둑에는 {self.wm}명의 선교사와 {self.wc}명의 식인종이 있다.\n"
                f"동쪽 강둑에는 {self.em}명의 선교사와 {self.ec}명의 식인종이 있다.\n"
                f"배는 {'서' if self.boat else '동'}쪽에 있다.")
    
    def goal_test(self) -> bool:
        return self.is_legal and self.em == MAX_NUM and self.ec == MAX_NUM

    @property
    def is_legal(self) -> bool:
        if self.wm < self.wc and self.wm > 0:
            return False
        if self.em < self.ec and self.em > 0:
            return False
        return True

    def successors(self) -> List[MCState]:
        sucs:List[MCState] = []
        if self.boat:   # 서쪽 강둑에 있는 배
            if self.wm > 1:
                sucs.append(MCState(self.wm - 2, self.wc, not self.boat))
            if self.wm > 0:
                sucs.append(MCState(self.wm - 1, self.wc, not self.boat))
            if self.wc > 1:
                sucs.append(MCState(self.wm, self.wc - 2, not self.boat))
            if self.wc > 0:
                sucs.append(MCState(self.wm, self.wc - 1, not self.boat))
            if (self.wc > 0) and (self.wm > 0):
                sucs.append(MCState(self.wm - 1, self.wc - 1, not self.boat))
        else:           # 동쪽 강둑에 있는 배
            if self.em > 1:
                sucs.append(MCState(self.wm + 2, self.wc, not self.boat))
            if self.em > 0:
                sucs.append(MCState(self.wm + 1, self.wc, not self.boat))
            if self.ec > 1:
                sucs.append(MCState(self.wm, self.wc + 2, not self.boat))
            if self.ec > 0:
                sucs.append(MCState(self.wm, self.wc + 1, not self.boat))
            if (self.ec > 0) and (self.em > 0):
                sucs.append(MCState(self.wm + 1, self.wc + 1, not self.boat))
        return [x for x in sucs if x.is_legal]

__init__: 사람 수와 보트의 위치를 설정한다.
__repr__: 강 양쪽의 사람 수를 출력한다.
goal_test: 모든 선교사와 식인종이 무사히 동쪽으로 이동했는지 확인한다.
is_legal: 강 어느 쪽이든 식인종의 수가 선교사의 수보다 많을 수 없도록 제한한다.
successors: 배에 탑승 가능한 모든 경우의 수를 리스트로 반환한다.

goal_test와 successors의 기능이 익숙하다. 우리는 이미 미로 찾기 알고리즘의 Maze 클래스에서도 동일한 메서드를 구현한 적 있다. 두 메서드는 앞서 구현한 탐색 알고리즘 함수의 인수로 들어갈 수 있다. 다시 말해서 선교사와 식인종 문제 역시 일반화를 적용할 수 있다는 것을 의미한다.

제네릭 프로그래밍의 힘

불필요한 이동이 발생하는 깊이 우선 탐색이나 휴리스틱을 요구하는 A* 알고리즘을 사용하는 대신, 너비 우선 탐색을 사용해 문제를 해결한다.

display_solution 메서드는 솔루션 경로를 출력하며, 미로 찾기 알고리즘의 Maze 클래스에서 구현한 mark 메서드와 유사한 기능을 한다.

def display_solution(path:List[MCState]):
    if len(path) == 0:
        return
    old_state:MCState = path[0]
    print(old_state)
    for current_state in path[1:]:
        if current_state.boat:
            print("{}명의 선교사와 {}명의 식인종이 동쪽 강둑에서 서쪽 강둑으로 갔다.\n"
                  .format(old_state.em - current_state.em, old_state.ec - current_state.ec))
        else:
            print("{}명의 선교사와 {}명의 식인종이 동쪽 강둑에서 서쪽 강둑으로 갔다.\n"
                  .format(old_state.wm - current_state.wm, old_state.wc - current_state.wc))
        print(current_state)
        old_state = current_state

사용자 지정 타입 T에는 MCState를, 나머지 두 인수로는 MCState의 클래스 메서드인 goal_test와 successors를 지정한다.

실행

if __name__ == "__main__":
    start:MCState = MCState(MAX_NUM, MAX_NUM, True)
    solution:Optional[Node[MCState]] = bfs(start, MCState.goal_test, MCState.successors)
    if solution is None:
        print("답을 찾을 수 없습니다.")
    else:
        path:List[MCState] = node_to_path(solution)
        display_solution(path)

서쪽 강둑에는 3명의 선교사와 3명의 식인종이 있다.
동쪽 강둑에는 0명의 선교사와 0명의 식인종이 있다.
배는 서쪽에 있다.
0명의 선교사와 2명의 식인종이 동쪽 강둑에서 서쪽 강둑으로 갔다.

...

서쪽 강둑에는 0명의 선교사와 0명의 식인종이 있다.
동쪽 강둑에는 3명의 선교사와 3명의 식인종이 있다.
배는 동쪽에 있다.

연습문제

📝 2-1

dna_search.py에서 숫자가 100만 개인 정렬된 리스트를 생성하라.

그리고 선형 검색의 linear_contains( )와 이진 검색의 binary_contains( ) 함수를 사용하여 몇몇 숫자를 찾는 데 걸리는 시간을 측정하라.

이진 검색의 시간복잡도는 O(logN)이므로, O(N)의 시간복잡도를 가지는 선형 검색에 비해 훨씬 효율적이다.

선형 검색	이진 검색
O(N)	O(logN)

두 검색 알고리즘의 효율 차이를 직관적으로 알 수 있도록 time 모듈을 사용해 특정 숫자를 찾는 데 걸리는 시간을 측정하며, 충분히 큰 크기의 리스트에서 검색을 실행한다.

from generic_search import linear_contains, binary_contains
import time

my_list = [x for x in range(1_000_000)]
test = [55555, 714285, 1000000]

선형 검색

for i in test:
    start = time.time()
    linear_contains(my_list, i)
    end = time.time()
    print(f"{i}를 찾는 데 걸리는 시간 : {(end - start) * 1000} ms")

55555를 찾는 데 걸리는 시간 : 1.9969940185546875 ms
714285를 찾는 데 걸리는 시간 : 21.904706954956055 ms
1000000를 찾는 데 걸리는 시간 : 33.91003608703613 ms

이진 검색

for i in test:
    start = time.time()
    binary_contains(my_list, i)
    end = time.time()
    print(f"{i}를 찾는 데 걸리는 시간 : {(end - start) * 1000} ms")

55555를 찾는 데 걸리는 시간 : 0.0 ms  
714285를 찾는 데 걸리는 시간 : 0.0 ms 
1000000를 찾는 데 걸리는 시간 : 0.0 ms

선형 검색에서는 N이 최대 100만이며, 숫자의 크기가 커질수록 검색에 필요한 비교 횟수가 많아지므로 검색하는 데 걸리는 시간은 숫자와 비례한다.

선형 검색 역시 빠른 속도로 이루어지지만, 이진 검색에서 logN은 20도 채 되지 않으므로 선형 검색과는 비교할 수 없을 정도로 빠르다.

📝 2-2

dfs( ), bfs( ), astar( ) 함수에 카운터를 추가하여 동일한 미로를 검색하는 지점의 수를 확인하라.

통게적으로 의미 있는 결과를 얻기 위해 100개의 미로 샘플에 대해 조사한다.

검색하는 지점의 수를 확인하기 위해 Node 클래스에 count 속성을 추가한 뒤, node_to_path 클래스에 이를 출력하기 위한 알고리즘을 작성한다.

class Node(Generic[T]):
    def __init__(self, state:T, parent:Optional[Node], cost:float = 0.0, heuristic:float = 0.0):
        self.state:T = state
        self.parent:Optional[Node] = parent
        self.cost:float = cost
        self.heuristic:float = heuristic
        self.count:int = 0 #★
    def __lt__(self, other:Node) -> bool:
        return (self.cost + self.heuristic) < (other.cost + other.heuristic)

def node_to_path(node:Node[T]) -> List[T]:
    counter:int = 0 #★
    path:List[T] = [node.state]
    while node.parent is not None:
        counter += node.count #★
        node = node.parent
        path.append(node.state)
    path.reverse()
    return counter #★

dfs( ), bfs( ), aster( ) 함수에서 자식 노드에 대한 비교를 수행할 때마다 해당 노드의 count를 1 증가시킨다.

def dfs
    ...
        for child in successors(current_state):
            current_node.count += 1 #★
            if child in explored:
    ...

def bfs
    ...
        for child in successors(current_state):
            current_node.count += 1 #★
            if child in explored:
    ...

def astar
    ...
        for child in successors(current_state):
            new_cost:float = current_node.cost + 1
            if child not in explored or explored[child] > new_cost:
                current_node.count += 1 #★
                explored[child] = new_cost
    ...

이제 세 알고리즘을 비교한다.

from typing import Dict

if __name__ == "__main__":
    main_count:int = 0
    solutions:Dict[str, int] = {"dfs" : 0, "bfs" : 0, "astar" : 0}
    while main_count < 100:
        m:Maze = Maze()
        solution1:Optional[Node[MazeLocation]] = dfs(m.start, m.goal_test, m.successors)
        solution2:Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successors)
        distance:Callable[[MazeLocation], float] = manhattan_distance(m.goal)
        solution3:Optional[Node[MazeLocation]] = astar(m.start, m.goal_test, m.successors, distance)
        if (solution1 and solution2 and solution3) is not None:
            main_count += 1
            solutions["dfs"] += node_to_path(solution1)
            solutions["bfs"] += node_to_path(solution2)
            solutions["astar"] += node_to_path(solution3)
    print(solutions)

{'dfs': 9493, 'bfs': 5149, 'astar': 2819}

탐색 불가능한 미로를 제외한 100개의 미로 샘플에 대해 조사했다.

조사 결과 dfs에서 가장 많은 지점(평균 94.9)을 검색했으며, astar에서 가장 적은 지점(평균 28.2)을 검색했다.

📝 2-3

선교사와 식인종 수를 변형하여 문제를 풀어보라.

선교사와 식인종의 수가 다른 경우에도 강을 건너는 방법을 출력해야 한다.

MISS:List[int] = []
CANN:List[int] = []

리스트 MISS와 CANN는 MCState 객체가 생성될 때마다 매개변수로 들어온 선교사와 식인종의 수를 저장한다. 리스트의 0번 인덱스는 처음 시작할 때 서쪽 강둑에 존재하는 선교사와 식인종의 수가 저장된다. 이후 기존 알고리즘의 MAX_NUM 대신 리스트의 0번 인덱스의 항목을 사용한다.

MCState 클래스의 내용을 수정한다.

def __init__(self, missionaries:int, cannibals:int, boat:bool) -> None:
        MISS.append(missionaries)
        CANN.append(cannibals)
        self.wm:int = missionaries
        self.wc:int = cannibals
        self.em:int = MISS[0] - self.wm
        self.ec:int = CANN[0] - self.wc
        self.boat:bool = boat

def goal_test(self) -> bool:
    return self.is_legal and self.em == MISS[0] and self.ec == CANN[0]

4명의 선교사와 3명의 식인종이 존재하는 경우 그에 맞게 인자를 수정한 수 실행한다.

실행

if __name__ == "__main__":
    start:MCState = MCState(4, 3, True)
    solution:Optional[Node[MCState]] = bfs(start, MCState.goal_test, MCState.successors)
    if solution is None:
        print("답을 찾을 수 없습니다.")
    else:
        path:List[MCState] = node_to_path(solution)
        display_solution(path)

서쪽 강둑에는 4명의 선교사와 3명의 식인종이 있다.
동쪽 강둑에는 0명의 선교사와 0명의 식인종이 있다.
배는 서쪽에 있다.
0명의 선교사와 2명의 식인종이 동쪽 강둑에서 서쪽 강둑으로 갔다.

...

서쪽 강둑에는 0명의 선교사와 0명의 식인종이 있다.
동쪽 강둑에는 4명의 선교사와 3명의 식인종이 있다.
배는 동쪽에 있다.