선교사 3명과 식인종 3명이 정원 2명짜리 배로 강을 건넌다. 어느 쪽 강가든 선교사가 있는데 식인종보다 적으면 안 된다.
무엇을 상태로 볼 것인가
강 양쪽의 인원 네 개와 배가 어느 쪽에 있는지를 묶으면 상황이 결정된다.
init = [3, 3, 0, 0]
goal = [0, 0, 3, 3]
왼쪽 선교사, 왼쪽 식인종, 오른쪽 선교사, 오른쪽 식인종 순서다. 배의 위치는 dir 로 따로 들고 다닌다.
cur_state = (dir, *cur)
if cur_state in path:
return
path.append(cur_state)
배 방향까지 넣어야 상태가 완성된다. 인원 배치가 같아도 배가 어느 쪽에 있느냐에 따라 다음에 할 수 있는 게 다르기 때문이다.
같은 상태에 다시 오면 그 뒤로 할 수 있는 것도 같다. 돌아가면 무한히 왔다 갔다 하게 되므로 거기서 끊는다.
방향을 부호로
건널 때마다 왼쪽에서 빼고 오른쪽에 더하거나, 그 반대를 해야 한다. 두 경우를 따로 쓰지 않고 dir 을 곱했다.
lm, lc, rm, rc = cur[0] - dir*m, cur[1] - dir*c, cur[2] + dir*m, cur[3] + dir*c
dir 이 1이면 왼쪽에서 오른쪽으로, -1이면 반대로 움직인다. 재귀할 때 -dir 을 넘겨 배를 되돌린다.
조건 두 개
c1 = lm >= 0 and lc >= 0 and rm >= 0 and rc >= 0
c2 = (lm == 0 or lm >= lc) and (rm == 0 or rm >= rc)
c1 은 인원이 음수가 되지 않는지 본다. 없는 사람을 태울 수는 없다.
c2 가 문제의 규칙이다. 각 강가에서 선교사 수가 식인종 수 이상이어야 하는데, 선교사가 0명이면 예외다. 선교사가 아무도 없으면 잡아먹힐 사람이 없다. lm == 0 or lm >= lc 의 앞부분이 그것이다.
이 예외를 빠뜨리면 3명이 전부 건너간 상태가 막혀서 답이 안 나온다.
태울 수 있는 조합을 미리 만들기
배에 몇 명을 어떻게 태울지는 매번 계산할 필요가 없다. 시작 전에 한 번 만들어둔다.
poss = []
for cur_man in range(1, man + 1):
for cur_mis in range(cur_man + 1):
cur_can = cur_man - cur_mis
if cur_mis >= cur_can or cur_mis == 0:
poss.append((cur_mis, cur_can))
배에 탄 인원 수를 1부터 정원까지 돌리고, 그 안에서 선교사를 몇 명 태울지 나눈다. 0명은 넣지 않는다. 배가 스스로 건너가지는 않는다.
배 위에서도 같은 규칙이 적용되므로 cur_mis >= cur_can or cur_mis == 0 으로 거른다. 정원 2명이면 다섯 가지가 나온다.
[(0, 1), (1, 0), (0, 2), (1, 1), (2, 0)]
path가 경로가 아니다
def mcp(cur, dir=1, path=[]):
기본 인자로 리스트를 뒀고 어디서도 pop 하지 않는다. 파이썬에서 기본 인자는 한 번만 만들어지므로 이 리스트는 호출 전체에서 공유된다.
그래서 path 는 지금까지 지나온 경로가 아니라 방문한 모든 상태의 목록이다. 중복 방문을 막는 용도로는 맞게 돌아가지만, 답을 찾았을 때 출력하는 path 는 해답 경로가 아니라 탐색 순서 전체다.
경로를 얻으려면 내려갈 때 넣고 돌아올 때 빼야 한다. 그러면 방문 기록은 따로 둬야 한다. 두 가지를 하나로 쓰고 있는 셈이다.