https://www.codingame.com/training/medium/river-crossing
문제요약
- 농부/늑대/염소/양배추가 강을 건넘
- 농부는 + 1을 갖고 강을 건널 수 있음
- 모든 상태는 조건을 지켜야함
- 농부가 없는 상태에서 늑대 + 염소 안됨
- 농부가 없는 상태에서 염소 + 양배추 안됨
- 상태표시는 L, R, L, R 같이 표시
- 시작상태 -> 끝 상태 가는 가장 짧은 경로, 짧은 경로가 여러개면 알파벳으로 앞서는 것접근법
- BFS + 경로 추적
- 어짜피 상태는 2^4 = 16개임
- python에서 방문 처리 + 경로 추적은 set으로 구현함
- 착각했던 점
- 어떤 상태로 오는 가지 수는 1개이므로 유일한 경로만 있을 것 같은데?
- 반례 L R L L => R R L R, L R L R => R R L R
- 농부의 상태를 봐서
- R이면 앞에서부터 L로 바꾸는 것이 유리하므로 앞에서부터 탐색
- L 이면 뒤에서부터 R로 바꾸는 것이 유리하므로 뒤에서부터 탐색
newbieski