Hamilton Path SRM452 Div2 Level3

그래프(adjacent matrix)에 대해 좀 연습할 수 있는 문제 - degree, cycle 등


어떤 국가에는 N개의 도시가 있고, 각 도시에는 0~N-1의 번호가 붙어있다.

각 도시끼리는 양방향 도로가 놓여있다.

다음과 같은 규칙으로 국가 내의 '모든' 도시를 여행하려고 한다.

- 1개의 도시에서 시작해 N-1개의 도로를 지나 모든 도시의 이동을 마친다.

- 각 도시는 한 번만 방문해야 한다.

- String[] roads가 주어진다. roads의 i번째 요소에 있는 j번째의 문자가 'Y'라면 존은 도시 i와 도시 j를 연결하는 도로를 반드시 지나야 한다.


예를들어, 3개의 도시가 있고, 존은 도시 0과 1을 연결하는 도로를 반드시 지나야 한다.

이런 경우, 4가지 방법이 있다. 0->1->2, 1->0-2, 2->0->1, 2->1->0 의 방법으로 모든 도시를 지날 수 있다.


존이 선택할 수 있는 경로의 수를 1000000007로 나눈 나머지를 리턴하라.


roads는 최대 50개의 요소를 가진다. (각 요소는 'Y'혹은 'N'이다)

[출처] 9. 해밀턴 패스 (graph, adjacent matrix, degree, cycle..)|작성자 송제인










엌ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 내가 이걸 이해하다니 ㅋㅋㅋㅋ