Is the Wall-Follower Algorithm in P?
Yes, there is a polynomial-time algorithm for solving perfect mazes: depth-first search solves them, and runs in polynomial time.  Actually, depth-first search is more general, as it can handle loops and other structures, too.

Breadth-first search also works, and will give you the fastest way out of the maze, but is only implementable on a computer given the full description of the maze.  In contrast, depth-first search can be implemented by a human with a piece of chalk and a ball of string -- the piece of chalk allows you to mark rooms as visited, and the ball of string lets you simulate the stack.