2251 물통

문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

====

문제 분석

하노이의 탑이랑 같은 유형의 문제이다. 

어떤 지점에서 다른 지점으로 물을 옮길 수 있냐를 묻는 문제 

각 물통에 담을 수 있는 물의 총량이 8 9 10이면, 처음에는 C에만 담겨 있으므로 [0,0,10] 을큐에 담아준다.

이 다음에 취할 수 있는 것은 c의 물을 a에 담기/b에 담기이다. 

그렇다면 [8,0,2] , [0,9,1]이라는 경우의 수가 나옴 

[8,0,2] 에서는 [0,8,2] , [0,0,10]이 나오는데 0,0,10은 중복 되니 배제 

[0,9,1] 에서는 [8,1,1] , [0,0,10] 이 나오는데 여기서도 0,0,10은 배제 

중복을 체크하는 방법은 3중 배열을 선언하여 체크 => visited[a][b][c] -> 여기서 a,b,c는 담을 수 있는 물의 총량

const LIMIT = input[0].split(' ').map((v) => +v);
const answer = [];
const q = [[0, 0, LIMIT[2]]];
const visited = Array.from({ length: LIMIT[0] + 1 }, () =>
    Array.from({ length: LIMIT[1] + 1 }, () =>
        Array.from({ length: LIMIT[2] + 1 }).fill(false)
    )
);
visited[0][0][LIMIT[2]] = true;

while (q.length) {
    const arr = q.shift();
    if (arr[0] === 0) {
        answer.push(arr[2]); 	// a가 0일때의 c의 물양을 출력해야 하므로 
    }
    for (let alpha = 0; alpha < 3; alpha++) {
        if (arr[alpha] === 0) continue;
        for (let otherAlpha = 0; otherAlpha < 3; otherAlpha++) {
            if (otherAlpha === alpha) continue;
            const diff = Math.min(
                LIMIT[otherAlpha] - arr[otherAlpha],
                arr[alpha]
            );
            const temp = arr.map((v, idx) => {
                if (idx === alpha) return v - diff;
                if (idx === otherAlpha) return v + diff;
                return v;
            });
            const [a, b, c] = temp;
            if (visited[a][b][c]) continue;
            visited[a][b][c] = true;
            q.push([a, b, c]);
        }
    }
}
console.log(answer.sort((a, b) => a - b).join(' '));

위에 선언 된 diff는 다른 위치로 물을 옮길 때 넘치면 안되어서 LIMIT-arr 을 해준 것이고,

이때 옮길 수 있는 물의 양보다 많은 양을 옮길 수는 없으므로 Math.min을 통해 작은 값을 옮겨준다.

정답 코드

const main = (input) => {
    const LIMIT = input[0].split(' ').map((v) => +v);
    const answer = [];
    const q = [[0, 0, LIMIT[2]]];
    const visited = Array.from({ length: LIMIT[0] + 1 }, () =>
        Array.from({ length: LIMIT[1] + 1 }, () =>
            Array.from({ length: LIMIT[2] + 1 }).fill(false)
        )
    );
    visited[0][0][LIMIT[2]] = true;
    while (q.length) {
        const arr = q.shift();
        if (arr[0] === 0) {
            answer.push(arr[2]);
        }
        for (let alpha = 0; alpha < 3; alpha++) {
            if (arr[alpha] === 0) continue;
            for (let otherAlpha = 0; otherAlpha < 3; otherAlpha++) {
                if (otherAlpha === alpha) continue;
                const diff = Math.min(
                    LIMIT[otherAlpha] - arr[otherAlpha],
                    arr[alpha]
                );
                const temp = arr.map((v, idx) => {
                    if (idx === alpha) return v - diff;
                    if (idx === otherAlpha) return v + diff;
                    return v;
                });
                const [a, b, c] = temp;
                if (visited[a][b][c]) continue;
                visited[a][b][c] = true;
                q.push([a, b, c]);
            }
        }
    }
    console.log(answer.sort((a, b) => a - b).join(' '));
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

main(input);