[LeetCode] 365. Water and Jug Problem

😎풀이

1. 두 주전자가 비어있는 상태 가정
2. 이미 확인했던 상태는 추가 탐색 생략
3. BFS 수행
   3-1. 현재 주전자 상태로 target과 동일해질 경우 true 반환
   3-2. 현재 주전자 상태를 저장
   3-3. 가능한 모든 경우의 수 queue에 추가 (물을 버릴 때, 가득 채울 때, 다른 쪽으로 부울 때)
4. 모든 경우의 수를 거쳤음에도 찾지 못할 경우 false 반환

function canMeasureWater(x: number, y: number, target: number): boolean {
    if((x + y) < target) return false
    const queue: [number, number][] = [[0, 0]]
    const seen: Set<string> = new Set()
    while(queue.length) {
        const [curX, curY] = queue.shift()
        if(curX === target || curY === target || curX + curY === target) return true
        const key = curX + ',' + curY
        if(seen.has(key)) continue
        seen.add(key)
        queue.push([0, curY])
        queue.push([curX, 0])
        queue.push([x, curY])
        queue.push([curX, y])
        const pourX = Math.min(curX, y - curY)
        const pourY = Math.min(curY, x - curX)
        queue.push([curX - pourX, curY + pourX])
        queue.push([curX + pourY, curY - pourY])
    }
    return false
};