Getting the map requires the actual tool you get from the dungeon, not the toy version of the one you have. (Which really shouldn't get replaced - Its alternate use is quite unique.) and extremely good timing with it. A mad dash, if you would. And even then, you'll have to bring the map to you with it.
Remember to look behind trees for walkable spaces. Go behind everything
Now, which miniboss was it that was a "puzzle" exactly? The only boss I fought was the vine/blue-spider miniboss, and that was nothing but a fight.
