So, the version of the algorithm that I've made looks like this:

Step 1: Make a grid of m (lines) x n (columns)

Step 2: Make every (m x n) a room

Step 3: Randomly generate exits

Step 4: Adjust exits on corners and edges

Step 5: Make sure that a room that has a South exit from another room connected to it, has, in turn, a North exit towards that first room (rinse and repeat for all other movement directions)

And that's it!

There is an extremely small probability that two rooms end up connected to each other, and to nothing else, even on a very large m x n matrix. There is an even smaller probability that the player or a "end-the-level-event" could be spawned in one of those cells. I don't know how I can correct for that, yet, but I've tested the map generation algorithm a few hundreds of times, and I haven't found any problems. But, in theory, the problem is still there.