게임 인공지능을 떠나 잠시 서치 알고리즘 문제를 예제와 함께 해결해 보겠다.
예전 주차에서 서치 알고리즘을 다루었었는데 사실 이 알고리즘을 길찾기 뿐만 아니라, 조건만 충족된다면 충분히 다른 경우에서도 사용이 될 수 있다는 것을 되새기기 위해 이런 포스팅을 적어본다. 이번 알고리즘 문제는 다양한 variation이 존재하는 알고리즘이며 강 건너기 라고도 예기한다. 이번 예제에서는 식인종과 선교사를 사용하도록 하겠다.
룰은 이러하다:
- 식인종과 선교사가 주어진 인원 수 만큼 왼쪽 섬에서 시작하여 오른쪽 섬으로 넘어가야 한다.
- 어느 순간에도 식인종의 수가 선교사의 수 보다 많아서는 안된다. (같은 수는 괜찮다)
- 배는 왼쪽섬에서 시작해서 오른쪽,왼쪽 섬을 번갈아가며 이동하는데, 최대 2명 최소 1명의 사람을 태우고 이동해야한다.
- 배가 각 차례때 이동시켜야하는 식인종과 선교사의 sequence를 리스트로 저장하여 반환하라. 이동 sequence가 다를 수는 있으나, 이동 수 자체는 최적화가 되어야 한다.
예시:
- (1,1) (식인종의 수, 선교사의 수) 라고 했을때 답은 [(1,1)] 이 된다
- (2,2) 라고 한다면 [(0, 2), (0, 1), (2, 0), (0, 1), (0, 2)] 가 되겠다.
이런식으로 좌->우, 좌<-우 를 보트로 옮겨다니며 사람을 옮기면 되는 게임이다. 이 알고리즘 문제를 priority queue와 서치 알고리즘을 활용해서 어떻게 접근 할 수 있을까?
식인종수 그리고 선교사 수는 인풋값으로 주어져 있다. 서치 알고리즘에서 했었던 것 처럼, 방문했던 state를 set값으로 저장하고, priority_queue를 생성하고, 마지막으로 starting state를 정의하는데 이 starting_state는 (보트가 움직인 횟수, 시작 선교사 수, 시작 식인종 수, 'left' (보트의 위치), [이 상태에 오기까지의 움직임]) 을 정보에 넣어준다. 이렇게 세팅이 되어 while priority_queue: 라는 구문으로 들어가게 된다.
while루프를 돌면서 보트의 움직임 수가 가장 작은 수 대로 뽑게 되는데, 만약 뽑았던 state의 값에서 왼쪽 섬에 있는 식인종 수, 왼쪽 선교사 수, 그리고 보트 위치값을 가져온 그 state가 이미 visited 에 들어가 있다면 루프를 넘기고, 없다면 그 고유의 값들은 visted set에 들어가게 된며 루프가 그래도 진행된다. possible moves 라는 리스트가 주어지는데 이는 한 턴에 옮길 수 있는 모든 사람의 경우의 수를 넣어놓은 리스트이다. 이 옮길 수 있는 모든 경우의 수 들을 가지고 루프를 돌며 이 옮기는 행위가 가능한지 (위의 주어진 조건을 violate 하는지 하지 않는지) 를 판단하여 priority queue에 집어 넣게 된다. 이렇게 루프를 돌아가면서 priority_queue를 지우고, 채워 넣고를 반복하다가 왼쪽 사람의 수가 0이 되면 그 즉시 루프를 탈출하여 그 state까지 오기까지의 움직임들을 반환한다. 만약 priority queue를 끝까지 다 서치했음에도 가능한 수 가 없다면 빈 리스트를 반환하면 해당 알고리즘의 작업이 완료된다.
보이는 것 처럼 아래의 값들을 돌렸을때, 최저의 수로 사람들을 옮기는 답안이 나오는 것을 알 수 있다. 
