8062 : 해밀턴 경로
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 도시와 도시들을 연결하는 $M$개의 단방향 도로가 주어집니다.
$1$번 도시에서 출발하여 모든 도시를 정확히 한 번씩만 방문하고, 마지막으로 $N$번 도시에 도착하는 경로의 총 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 16$
• $1 \le M \le 200$
• $1 \le u, v \le N$
$1$번 도시에서 출발하여 모든 도시를 정확히 한 번씩만 방문하고, 마지막으로 $N$번 도시에 도착하는 경로의 총 개수를 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 16$
• $1 \le M \le 200$
• $1 \le u, v \le N$
입력 설명
첫째 줄에 도시의 개수 $N$과 도로의 개수 $M$이 공백으로 구분되어 주어집니다. ($2 \le N \le 16$, $1 \le M \le 200$)
둘째 줄부터 $M$개의 줄에 걸쳐 도로의 시작 도시 $u$와 도착 도시 $v$가 공백으로 구분되어 주어집니다. ($1 \le u, v \le N$)
둘째 줄부터 $M$개의 줄에 걸쳐 도로의 시작 도시 $u$와 도착 도시 $v$가 공백으로 구분되어 주어집니다. ($1 \le u, v \le N$)
출력 설명
$1$번 도시에서 출발하여 모든 도시를 정확히 한 번씩 방문한 후 $N$번 도시에 도달하는 경로의 수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 6
1 2
1 3
2 3
2 4
3 2
3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
도시의 개수가 최대 $16$개이므로 비트마스크(Bitmask)를 이용한 동적 계획법(DP)을 사용합니다.
$dp[mask]$는 방문한 도시 집합이 $mask$이고, 현재 $u$번 도시에 있을 때 가능한 경로의 수로 정의할 수 있습니다. 단, $N$번 도시는 마지막에만 방문해야 하므로 중간 과정에서 $N$번에 도달하는 전이는 제외해야 합니다.
$dp[mask]$는 방문한 도시 집합이 $mask$이고, 현재 $u$번 도시에 있을 때 가능한 경로의 수로 정의할 수 있습니다. 단, $N$번 도시는 마지막에만 방문해야 하므로 중간 과정에서 $N$번에 도달하는 전이는 제외해야 합니다.