N*N*N짜리의 정육면체로 이루어진 미로가 있다.

미로의 시작점은 좌표(1,1,1)이고 도착점은 좌표(N, N, N)가 된다. (x, y, z)좌표에 위치하였을 경우 이동 가능한 좌표는 (x+1,y, z), (x, y+1, z), (x, y, z+1)이다. 어떤 미로의 좌표에 다다르게 되면 ‘(’ 혹은 ‘)’, 그리고 ‘.’ 문자가 주어지는데, 도착한 순서대로 해당 문자를 이어 붙여 괄호 쌍을 만들게 되는데, 시작점에서 출발하여 도착점에 다다랐을 때 만들어진 문자열이 반드시 올바른 괄호쌍이 만들어져야 한다.

올바른 괄호쌍이란 괄호 쌍을 여는 기호와 닫히는 기호가 제대로 맞물려 있는 것을 의미하며 미로 안의 문자열에서 ‘(’는 여는 기호 ‘)’는 닫는 기호, 그리고 ‘.’의 경우는 여는 기호와 닫는 기호도 아닌 넘어가는 기호가 된다.

“(..)...()”은 올바른 괄호 쌍이 될 수 있지만, “(()...”와 같은 경우는 제대로 맞물려 있지 않기 때문에 올바른 괄호 쌍이 될 수 없다.

임의의 미로가 주어졌을 때, 시작점부터 도착점까지 갈 수 있는 방법이 몇 가지인지 알아보는 프로그램을 출력하라.

#1361 upload 114 done 26 how_to_reg 19

괄호 미로 timer 1s memory 64MB

#1361

괄호 미로 1s 64MB