이 문제를 처음본다면 좀 막막할 수 있습니다.

어쩌면 (0,0)에는 1번, (0,1)에는 1번, 어디에는 빈칸, ... -> 오케이! 이건 되는구나! 그럼 답은 +1이야
이런 방법으로 접근하는 방법을 생각해 볼 수 있을겁니다. 당연히 시간초과가 나겠군요.

여기서 좀 더 나아간다면, 적어도 선로를 배치하는 것은 언제 하던지 사실 상관 없다는 것을 알 수 있습니다. 선로를 배치하고 경로를 검증하는 것이 아니라 경로가 검증된 선로만 배치하는 것입니다. 0,0에서 시작해서 다음 선로 놓는 걸 선로의 진행 방향에 의해 결정하는 방법을 취할 수 있습니다. 이러면 백트래킹 기법을 가미한 깊이우선탐색이 될 것입니다.

문제는 3번 선로의 존재입니다. 3번을 깔면 해당 지점을 다시 와야 한다는 점 때문에, 지나가야 하는 점의 수를 늘린다 등과 같은 꼼수를 써도 굉장히 답답한 그림이 나옵니다. 쓸데없이 탐색하는 지점이 커집니다. 직선 선로와 십자 선로의 경로는 유사한데, 어떻게 한번에 처리하는 방법이 없을까요?

여기서 선로 중심의 접근보다 경로 중심의 접근방법을 생각해 볼 수 있습니다. 경로에 대응하는 선로 배치방법은 한 가지 뿐입니다. 서로 다른 경로를 동일 배치로 처리할수도 없고, 동일 선로 배치를 서로 다른 방법의 경로로 갈 수도 없습니다.
시작점에서 끝점 까지의 경로의 수를 찾는데, 진행 방향이 바뀌는 커브 지점에는 한 번만 통과할 수 있고, 직선지점은 두 번 통과할 수 있습니다.

십자 경로의 경우 어떤 지점을 좌에서 우로 통과하고는, 다시 우에서 좌 또는 좌에서 우로 통과하는 경우가 나오는게 아닌가? 라고 생각할 수도 있습니다만, 커브는 한 번 돌면 다시 그 지점을 지나칠 수 없기 때문에 그런 일은 발생하지 않습니다.

즉, 깊이우선 탐색으로 각 탐색에 있어서 이전지점 정보와 현재 지점 정보를 바탕으로 다음 지점 3곳을 결정하여 탐색을 진행합니다.
이중 한 곳은 현 지점에 깔리는 타일의 종류가 직선도로입니다. 이 경우 해당 지점을 한번 더 갈 수 있다는 표시를 해 줍니다. 커브는 더이상 갈 수 없다는 마킹을 해 줍니다.
이후 직선으로 한 번 지나간 지점을 탐색하게 된다면 무조건 직진으로 한 가지 방향으로 탐색이 정해지며, 해당 지점은 탐색 불가 지점이 되도록 하면 됩니다.

그럼 배치된 타일들은 어떻게 처리해야 할까요?
이 타일들 중 3번은 두 개의 카운팅을 하고, 나머지는 한 번의 카운팅을 하여 지나쳐야 할 지점의 수를 계산해 둡니다.
각 지점을 지나칠 때, 이전 탐색 지점을 바탕으로 선로가 연결되었을 경우 다음 지점으로 탐색을 이어나가며 카운팅을 하나 내려줍니다.
종점에 도착했을 때, 카운팅의 수에 따라 문제의 답을 1 증가시키거나 그대로 둡니다.

즉, 방문여부를 체크하는 곳에 직선으로 한번 더 갈 수 있음과 (직선 두번 또는 곡선 한번으로)더이상 갈 수 없음, 아직 안 감만 기록한다면 7종류의 타일을 다루는 것이 아니라 2종류의 타일을 다루는 것으로 바뀝니다.

물론 처음부터 있었던 타일은 7종류로 잘 처리해야 하겠습니다.

재미있지만 좀 더러운 문제네요.