A robot cleaner that cleans a cleaning region while traveling the cleaning region and a method to control the same are provided. The robot cleaner can uniformly clean a cleaning region based on a wall-following technique which allows the robot cleaner to travel along the outline of the cleaning region. The method selects, as a reference wall, a wall at a left or right side of the robot cleaner at a start position of the robot cleaner based on a left or right-based travel algorithm, which allows the robot cleaner to travel along a left or right wall, and controls the robot cleaner to travel the cleaning region in a zigzag travel pattern in which the robot cleaner moves a predetermined distance in a direction perpendicular to the reference wall at specific intervals along the selected reference wall while following the selected reference wall.