선교사와 식인종
선교사와 식인종 문제 풀이
인공지능을 배우다 보면 마주하게 되는 제약 조건 만족 문제.
초기 상태와 목표 상태를 명확하게 정의하고 조건을 검사하며 진행해야 한다.
풀이 코드
Python을 이용해 BFS 알고리즘을 구현하였다.
BFS 구현을 위한 queue(deque) 사용
from collections import deque
# deque을 queue로 사용
deque = deque()
초기 변수 선언 및 초기화
# (왼쪽 선교사, 식인종, 오른쪽 선교사, 식인종, 보트 위치(0:왼쪽, 1:오른쪽))
initial_state = (3, 3, 0, 0, 0)
deque.append(initial_state)
# 이동할 수 있는 경우의 수 (순서 변경 시 다른 최적 경로 탐색 가능)
moves = ((1, 0), (2, 0), (1, 1), (0, 1), (0, 2))
# 이미 탐색한 경로 메모
memos = set([initial_state])
# 경로를 저장할 딕셔너리
parent_map = {initial_state : None}
각 인원이 3명을 초과하거나 음수가 되지 않는지 검사, 식인종이 선교사보다 많지 않은지(문제의 제약 조건) 검사
# 다음 상태가 유효한지 판단하는 함수
def is_valid(state) :
lm, lc, rm, rc, b = state
if not(0 <= lm <= 3 and 0 <= lc <= 3 and 0 <= rm <= 3 and 0 <= rc <= 3) :
return False
if lm > 0 and lm < lc :
return False
if rm > 0 and rm < rc :
return False
return True
moves에 저장해둔 이동 가능 경우의 수를 이용하여 현재 상태에서 다음 상태로 넘어갈 때 가능한 모든 경우의 수 중에 유효한 상태만을 추출
# 다음 상태의 모든 경우의 수 반환
def move(state) :
lm, lc, rm, rc, b = state
next_states = []
for m, c in moves :
if b == 0 :
new_state = (lm - m, lc - c, rm + m, rc + c, 1)
else :
new_state = (lm + m, lc + c, rm - m, rc - c, 0)
if is_valid(new_state) :
next_states.append(new_state)
return next_states
queue를 이용한 메인 루프(BFS)
# BFS 탐색
while deque :
tmp = deque.popleft()
print(f"왼쪽 :\t선교사 * {tmp[0]}, 식인종 * {tmp[1]}")
print(f"오른쪽 :\t선교사 * {tmp[2]}, 식인종 * {tmp[3]}")
if tmp[4] == 0 :
print("보트 :\t왼쪽")
else :
print("보트 :\t오른쪽")
print("---------------------------------------")
if tmp == (0, 0, 3, 3, 1) :
break
next_states = move(tmp)
for state in next_states :
if state not in memos :
memos.add(state)
deque.append(state)
parent_map[state] = tmp
루프 종료 이후 최종 경로 추출, 출력
# 탐색 성공 후 결과 출력
if tmp == (0, 0, 3, 3, 1) :
print("탐색 성공")
path = []
curr = tmp
while curr is not None:
path.append(curr)
curr = parent_map[curr]
path.reverse()
print("\n=== 최종 경로 ===")
print("---------------------------------------")
for i, step in enumerate(path) :
lm, lc, rm, rc, b = step
if b == 0 : boat = "왼쪽"
else : boat = "오른쪽"
print(f"{i+1}\n왼쪽 :\t선교사 * {lm}, 식인종 * {lc}")
print(f"오른쪽 :\t선교사 * {rm}, 식인종 * {rc}\n보트 :\t{boat}")
print("---------------------------------------")
else :
print("탐색 실패")
결과
=== 최종 경로 ===
---------------------------------------
1
왼쪽 : 선교사 * 3, 식인종 * 3
오른쪽 : 선교사 * 0, 식인종 * 0
보트 : 왼쪽
---------------------------------------
2
왼쪽 : 선교사 * 2, 식인종 * 2
오른쪽 : 선교사 * 1, 식인종 * 1
보트 : 오른쪽
---------------------------------------
3
왼쪽 : 선교사 * 3, 식인종 * 2
오른쪽 : 선교사 * 0, 식인종 * 1
보트 : 왼쪽
---------------------------------------
4
왼쪽 : 선교사 * 3, 식인종 * 0
오른쪽 : 선교사 * 0, 식인종 * 3
보트 : 오른쪽
---------------------------------------
5
왼쪽 : 선교사 * 3, 식인종 * 1
오른쪽 : 선교사 * 0, 식인종 * 2
보트 : 왼쪽
---------------------------------------
6
왼쪽 : 선교사 * 1, 식인종 * 1
오른쪽 : 선교사 * 2, 식인종 * 2
보트 : 오른쪽
---------------------------------------
7
왼쪽 : 선교사 * 2, 식인종 * 2
오른쪽 : 선교사 * 1, 식인종 * 1
보트 : 왼쪽
---------------------------------------
8
왼쪽 : 선교사 * 0, 식인종 * 2
오른쪽 : 선교사 * 3, 식인종 * 1
보트 : 오른쪽
---------------------------------------
9
왼쪽 : 선교사 * 0, 식인종 * 3
오른쪽 : 선교사 * 3, 식인종 * 0
보트 : 왼쪽
---------------------------------------
10
왼쪽 : 선교사 * 0, 식인종 * 1
오른쪽 : 선교사 * 3, 식인종 * 2
보트 : 오른쪽
---------------------------------------
11
왼쪽 : 선교사 * 1, 식인종 * 1
오른쪽 : 선교사 * 2, 식인종 * 2
보트 : 왼쪽
---------------------------------------
12
왼쪽 : 선교사 * 0, 식인종 * 0
오른쪽 : 선교사 * 3, 식인종 * 3
보트 : 오른쪽
---------------------------------------