This trophy is made easy once you've entered the post-game. The story is fairly streamlined, so you aren't really given much of a choice regardless. Once you've beaten the game, move through the village until you reach a square plaza. You'll see Shikaku with a purple request icon over his head, this is where you commence the Ninja World Timeline search. Near the exist on this side of the plaza is a girl with an icon over her head. She'll let you teleport anywhere you'd like for a fee. If you've cleared the main game, you should only really need to go to the Village Hidden In The Clouds. If this doesn't unlock your trophy, make your way down the list and it should pop with one of the villages.