문제 정의

세 명의 상인과 각각 한 명의 수행원이 강을 건너야 한다. 작은 배는 최대 두 사람만 탑승할 수 있으며, 상인들이 직접 조종해야 한다. 강의 어느 쪽이든 수행원 수가 상인 수보다 많아지면 상인들을 해칠 계획이다. 상인들이 안전하게 강을 건너려면 어떻게 해야 할까?

수학적 모델링

이 문제를 해결하기 위해 깊이 우선 탐색(DFS) 알고리즘을 적용한다. 선박의 적재 용량이 2명일 때 가능한 모든 이동 상태와 상인과 수행원의 안전한 수치 조합을 미리 정의한다. 탐색 과정에서 경로를 기록하며, 왼쪽 강변에 아무도 남지 않은 상태를 찾으면 즉시 탐색을 종료하고 해결책을 출력한다.

변수 정의

Path: 단계별 경로를 저장하는 배열
PossibleMoves: 가능한 이동 방법들을 정의
SafetyCheck: 현재 상태의 안전 여부를 판단
VesselPosition: 현재 배의 위치(건너감 또는 돌아옴)

실행 결과

총 11단계로 해결 가능

• 1단계: 수행원 두 명이 건넌다
• 2단계: 수행원 한 명이 다시 돌아온다
• 3단계: 수행원 두 명이 다시 건넌다
• 4단계: 수행원 한 명이 다시 돌아온다
• 5단계: 상인 두 명이 건넌다
• 6단계: 수행원 한 명과 상인 한 명이 돌아온다
• 7단계: 상인 두 명이 건넌다
• 8단계: 수행원 한 명이 돌아온다
• 9단계: 수행원 두 명이 건넌다
• 10단계: 수행원 한 명이 돌아온다
• 11단계: 마지막으로 수행원 두 명이 건넌다

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

const int PossibleMoves[5][2] = {{0, 2}, {1, 1}, {2, 0}, {0, 1}, {1, 0}};
const bool SafetyCheck[4][4] = {{0, 0, 0, 0}, {1, 0, 1, 1}, {1, 1, 0, 1}, {0, 0, 0, 0}};

int Path[1001][2], currentStep = 1;
bool VesselPosition[1001], solutionFound = false;

bool hasDuplicate(int merchants, int servants, bool position) {
    for(int idx = 0; idx < currentStep; idx++) {
        if(merchants == Path[idx][0] && servants == Path[idx][1] && VesselPosition[idx] == position) 
            return true;
    }
    return false;
}

bool isUnsafe(int traders, int attendants, bool position) {
    if (traders < 0 || traders > 3 || attendants < 0 || attendants > 3 || SafetyCheck[traders][attendants] || hasDuplicate(traders, attendants, position)) 
        return true;
    return false;
}

void exploreSolution(int merchantCount, int servantCount) {
    if(!merchantCount && !servantCount) {
        cout << currentStep - 1 << endl;
        cout << "(왼쪽상인,왼쪽수행)" << " " << "(오른쪽상인,오른쪽수행)" << endl;
        for (int idx = 0; idx < currentStep; idx++) {
            cout << "(" << Path[idx][0] << "," << Path[idx][1] << ") ";
            cout << "(" << 3 - Path[idx][0] << "," << 3 - Path[idx][1] << ")" << endl;
        }
        exit(0);
    }
    else if (!solutionFound) {
        for (int moveIdx = 0; moveIdx <= 4; moveIdx++) {
            merchantCount -= PossibleMoves[moveIdx][0];
            servantCount -= PossibleMoves[moveIdx][1];
            
            if (isUnsafe(merchantCount, servantCount, solutionFound)) {
                merchantCount += PossibleMoves[moveIdx][0];
                servantCount += PossibleMoves[moveIdx][1];
                continue;
            }
            
            Path[currentStep][0] = merchantCount;
            Path[currentStep][1] = servantCount;
            VesselPosition[currentStep] = solutionFound;
            
            currentStep++;
            solutionFound = (!solutionFound);
            exploreSolution(merchantCount, servantCount);
            solutionFound = (!solutionFound);
            
            merchantCount += PossibleMoves[moveIdx][0];
            servantCount += PossibleMoves[moveIdx][1];
            currentStep--;
        }
    }
}

int main() {
    Path[0][0] = Path[0][1] = 3;
    VesselPosition[0] = true;
    exploreSolution(3, 3);
    return 0;
}

Python 구현 코드

PossibleMoves = [(0, 2), (1, 1), (2, 0), (0, 1), (1, 0)]
SafetyCheck = [[0, 0, 0, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 0, 0, 0]]

Path = [[0, 0] for _ in range(1001)]
VesselPosition = [False] * 1001
currentStep = 1
solutionFound = False

def hasDuplicate(merchants, servants, position):
    for idx in range(currentStep):
        if merchants == Path[idx][0] and servants == Path[idx][1] and VesselPosition[idx] == position:
            return True
    return False

def isUnsafe(traders, attendants, position):
    if traders < 0 or traders > 3 or attendants < 0 or attendants > 3 or SafetyCheck[traders][attendants] or hasDuplicate(traders, attendants, position):
        return True
    return False

def exploreSolution(merchantCount, servantCount):
    global currentStep, solutionFound
    
    if not merchantCount and not servantCount:
        print(currentStep - 1)
        print("(왼쪽상인, 왼쪽수행) (오른쪽상인, 오른쪽수행)")
        for idx in range(currentStep):
            print(f"({Path[idx][0]}, {Path[idx][1]}) ({3 - Path[idx][0]}, {3 - Path[idx][1]})")
        exit(0)
    
    if not solutionFound:
        for moveIdx in range(5):
            merchantCount -= PossibleMoves[moveIdx][0]
            servantCount -= PossibleMoves[moveIdx][1]
            
            if isUnsafe(merchantCount, servantCount, solutionFound):
                merchantCount += PossibleMoves[moveIdx][0]
                servantCount += PossibleMoves[moveIdx][1]
                continue
            
            Path[currentStep][0] = merchantCount
            Path[currentStep][1] = servantCount
            VesselPosition[currentStep] = solutionFound
            
            currentStep += 1
            solutionFound = not solutionFound
            exploreSolution(merchantCount, servantCount)
            solutionFound = not solutionFound
            
            merchantCount += PossibleMoves[moveIdx][0]
            servantCount += PossibleMoves[moveIdx][1]
            currentStep -= 1

if __name__ == "__main__":
    Path[0][0] = Path[0][1] = 3
    VesselPosition[0] = True
    exploreSolution(3, 3)