This is not really a "problem." OK, it is a problem for you, but it is how it is supposed to work.
When you weight paint, you are adding weights to the vertices, not the faces. So anywhere you have faces sharing a vertex, you are going to have the weights "bleed" to the other face.
In that picture the two cubes share two vertices. On the left is what I selected and applied a weight of one; on the right are the weights.
The simplest way to remedy your situation is to disconnect the two faces.
Select the vertices shared by the two different parts and press V, without doing anything else press Esc or right click to cancel the transform.
Now hover over the part that should have zero weights, and press L to select linked. In the Data tab of the properties panel assign that selection a weight of zero.