bfs 안에서 enqueue의 매개변수

안녕하세요 큰돌님

강의를 듣다 이해가 안되는게 있어 질문드립니다.

bfs안에서 4개의 enqueue는 A,B의 물통을 채우고, 비우는것으로 이해했는데

enqueue(waterA, y, mp[{x,y}]); // A의 물통을 채운것
enqueue(x, waterB, mp[{x,y}]); // B의 물통을 채운것
enqueue(0, y, mp[{x,y}]); // A의 물통을 비운것
enqueue(x, 0, mp[{x,y}]); // B의 물통을 비운것

아래 enqueue 함수의 매개변수들이 왜 min(), max()로 하신건지 이해를 못하겠습니다.

A -> B로 이동

B -> A로 이동 시키는것 같은데
매개변수가 왜 아래와 같이 들어가는지 이해하지 못하겠습니다.

enqueue(min(x + y, waterA), max(0, x + y - waterA), mp[{x,y}]);
enqueue(max(0, x + y - waterB), min(x + y, waterB), mp[{x,y}]);

혹시 추가적으로 설명해 주실수 있을까요?

안녕하세요 ㅎㅎ SOL님

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();  
        ... 
        enqueue(min(x + y, a), max(0, x + y - a), m[{x, y}]);
        enqueue(max(0, x + y - b), min(x + y, b), m[{x, y}]); 
    }

이부분 말씀하시는거죠?

이부분은 이걸 표현한 코드입니다.

[M(x,y): Move water from x to y)]: 물통 x의 물을 물통 y에 붓는다. 이때 만약 물통 x에 남아 있는 물의 양이 물통 y에 남아 있는 빈 공간보다 적거나 같다면 물통 x의 물을 물통 y에 모두 붓는다. 만약 물통 x에 남아 있는 물의 양이 물통 y에 남아 있는 빈 공간보다 많다면 부을 수 있는 만큼 최대로 부어 물통 y를 꽉 채우고 나머지는 물통 x에 남긴다.

자 x, y 는 a, b에 각각 남아있는 물의 양입니다.

여기서 x + y를 통해 b에 남아있는 물을 a로 옮깁니다. 그 때 a의 최대값을 넘길 수는 없겠죠?

또한, 만약 x + y를 통해 b에 남아있는 물을 a로 넘기는데 이부분이 a보다 클 경우 해당 남아있는 부분을 y에다가 남깁니다. max를 줘서 만약 a가 클경우에 if문을 주지 않고, 마이너스가 될 경우 0과 max를 넣어 범위를 0 ~ 양수로 만드는 코드입니다.

enqueue(min(x + y, a), max(0, x + y - a), m[{x, y}]);

그림을 한번 그려볼까요?

이렇게 되는 코드입니다.

참고로 max(0, value) 이코드는 꼭 기억해주세요ㅎㅎ 범위 자체를 0 ~ 양수로 만들어버리는 코드입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변