How do I stop the dog from eating the space fleet

Hint 1 of 5:

Did you save your game often?

Hint 2 of 5:

Do you remember the bar, and a similar dog?

Hint 3 of 5:

Buy the cheese sandwich at the bar.

Hint 4 of 5:

Feed the cheese sandwich to the hungry dog on your way out.