몇 개의 정점으로 이루어진 트리가 있다. 이 트리는 루트가 있는 트리이며, 각 정점은 몇 개의 자식 정점을 가질 수 있다. 각각의 정점에는 알파벳 대문자가 적혀 있다. 같은 문자가 여러 정점에 적혀 있을 수도 있다.

이 트리를 루트부터 시작해서 탐색하는데, 어떤 한 정점에서는 그 정점의 자식들 중 왼쪽 자식들부터 차례대로 방문해 나간다. 이와 같이 탐색하면 하나의 경로를 얻을 수 있다. 주의할 점은, 자식이 있는 정점의 경우에는 여러 번 방문될 수도 있는데(제일 처음 방문할 때와, 자식 정점을 방문하고 다시 돌아올 때), 그러한 경우에 한 정점이 여러 번 경로에 나타날 수도 있다는 것이다.

위의 그림은 경로가 ABABABA인 경우를 모두 나타낸 것이다. 아래쪽이 루트를 의미하며, 위로 연결된 것이 자식 노드를 의미한다. 위의 그림에서는 왼쪽 자식을 왼쪽에 나타냈는데, 대부분의 사람이 생각하는 그림처럼 루트가 위에 있는 그림으로 고치려면, 좌우 대칭을 해야 한다. 물론 답에는 변화가 없다.

경로가 주어졌을 때, 그러한 경로를 갖는 트리의 개수를 구해내는 프로그램을 작성하시오.

#8274 upload 2 done 1 how_to_reg 1

오일러(Euler) 탐색 timer 1s memory 1024MB

#8274

오일러(Euler) 탐색 1s 1024MB