2005학년도 10월 고3 전국연합학력평가 수학 영역 나형 15번

[그림1]과 같이 네 개의 방이 통로로 연결되어 있을 때, 어느 한 방에서 출발하여 모든 방을 한 번만 방문하는 방법의 수는 출발하는 방의 경우의 수가 $4$ (가지)이고 각 경우에 모든 방을 방문하는 방법의 수는 $2$ (가지)이므로, $4\times2=8$ (가지)이다.

[그림2]와 같이 $6$개의 방이 통로로 연결되어 있을 때, 어느 한 방에서 출발하여 모든 방을 한 번만 방문하는 방법의 수는? [4점]