방 모두 한 번 방문

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

[그림$1$] [그림$2$] [그림$2$]와 같이 $6$개의 방이 통로로 연결되어 있을 때, 어느 한 방에서 출발하여 모든 방을 한 번만 방문하는 방법의 수는? [4점] ①$12$가지②$14$가지③$15$가지④$16$가지⑤$18$가지