지도 색칠하기 Batch Compilation commands

4색 정리가 증명되었지만 사실 지도와 4색 정리는 큰 연관이 없고, 대부분의 지도 제작자들은 지도를 제작할 때 색을 최소한으로 사용하려는 노력을 크게 하지 않는다고 합니다.

이에 승현이는 고정관념을 깨트리기 위해 4가지의 색으로 지도를 색칠하기로 하고, 아래의 4가지 색을 선택했습니다. 단, 지도를 색칠할 때 인접한 국가들끼리는 다른 색을 칠해야 하고, 같은 국가에는 같은 색을 칠해야 합니다.

그런데 생각해 보니, 강과 바다는 무조건 파란색으로 칠해야 했고, 그래서 4가지 색으로 지도를 색칠하기에는 역부족이었습니다.

좋은 방법이 없을까 생각하던 승현이는 결국 노랑, 연두, 초록, 파랑, 주황의 5가지 색으로 지도를 색칠하기로 했습니다. 강과 바다는 파란색으로 칠해야 하므로, 육지를 칠하는 데 사용할 수 있는 색은 파란색을 제외한 4개뿐입니다.

문제는, [그림 1]과 같이 한 나라가 여러 동강이 나 있을 수도 있다는 것입니다. (식민지를 건설한다거나, 땅을 사고판다거나, ..)

이런 경우, 위에 명시된 대로 같은 국가에 같은 색, 위 그림에서는 2번 국가에 같은 색을 칠해야 합니다. 따라서 [그림 2]와 같이 지도를 색칠할 수 없습니다.

해야 할 일

당신은 주어진 지도를 위 조건을 만족하면서 5가지 색으로 색칠할 수 있는 모든 경우의 수를 반환하는 함수 NumberOfMaps(N, M, A, B)를 작성해야 합니다. (뜬금없죠? ..근데 딱히 연관지을 게 없어서..)

• **N**은 지도 위에 그려진 바다 위에 떠 있는(?) 국가의 수입니다.
• **M**은 지도에서 국경이 인접한 국가들의 쌍의 수이며, 0 ≤ M ≤ N(N-1)/2임이 보장됩니다.
• **A**와 **B**는 M의 크기를 갖는 배열입니다. 임의의 i (0 ≤ i ≤ N - 1)에 대해, A[i]번 국가와 B[i]번 국가의 국경은 인접해 있습니다. 국가들의 번호는 1 이상 N 이하의 자연수들로 구성됩니다. 단, M = 0인 경우 크기가 1인 배열이 주어지며, 배열에 담긴 값은 무시해야 합니다.

서브태스크

서브태스크 1 (10점)

$1 \le \ N \le 8.$

서브태스크 2 (20점)

$1 \le \ N \le 11.$

서브태스크 3 (25점)

$1 \le \ N \le 14.$

서브태스크 4 (30점)

$1 \le \ N \le 17.$

서브태스크 5 (35점)

$1 \le \ N \le 20.$

예제

예제 1 (example1.in, example1.out)

아래 인터페이스에 주어지는 1번 예제는 위 그림을 표현한 것입니다. 색칠할 수 있는 경우의 수는 $4 \times 3 = 12$가지입니다.

예제 2 (example2.in, example2.out)

아래 인터페이스에 주어지는 2번 예제는 위 그림을 표현한 것입니다. 색칠할 수 있는 경우의 수는 $4 \times 3 \times 2 \times 4 = 96$가지입니다.

구현 시 유의사항

채점 환경

• 프로그램의 최대 실행 시간은 1.5초입니다. 채점 프로그램의 실행 시간이 0.1초를 넘지 않음이 보장되어 있습니다.
• 메모리 제한은 64MB이며, 스택 메모리 역시 전체 메모리에 포함됩니다.

인터페이스

문제에 제시된 첨부파일 grader.zip에서 개발에 필요한 인터페이스가 제공됩니다. 이를 이용해서 이 문제를 좀 더 쉽게 해결할 수 있을 것입니다. 아래에 그 설명이 있습니다.

• 작성해야 할 파일: map.c 또는 map.cpp
• 견본 채점 프로그램: grader.c 또는 grader.cpp
• 컴파일 쉘(gcc): compile_c.sh 또는 compile_cpp.sh
• 입력 예제 1: example1.in, example1.out
• 입력 예제 2: example2.in, example2.out

견본 채점 프로그램은 표준 입력(stdin)으로 입력을 받으며, 그 양식은 아래와 같습니다.

• 1번째 줄: N과 M이 공백을 사이로 두고 주어집니다.
• 2~M+1번째 줄: i + 2번째 줄에 A[i]와 B[i]가 공백으로 분리되어 주어집니다.

견본 채점 프로그램은 표준 출력(stdout)으로 NumberOfMaps 함수의 반환값을 출력합니다.