Yukicoder No. 95 Alice and Graph

Yukicoder No. 95 Alice and Graph

문제 링크

문제

Alice는 생일 선물로 방향성이 없는 그래프를 받았습니다. 그리고 평소처럼 그래프를 가지고 게임을 합니다.

 

그래프는 $N$ 개의 정점이 있고, $1$번부터 $N$번까지 번호가 붙어있으며, $k$번 정점에는 $2^{k-1}-1$ 개의 동전이 있습니다.

게임을 시작할 때, Alice는 $1$번 정점에 있습니다. $2^{1-1}-1=0$이기 때문에, $1$번 정점에는 동전이 없습니다.

그리고 Alice는 최대 $K$번 이동할 수 있습니다.

각 이동에서, Alice는 간선을 따라 인접한 정점으로 이동할 수 있고, 정점에 있는 동전을 수집할 수 있습니다.

(주: 같은 정점을 두 번 방문하는 경우에도, 동전은 한 번만 수집할 수 있습니다.)

Alice가 수집할 수 있는 동전의 최대 개수는 몇 개일까요?

Alice가 $1$번 정점으로 돌아가지 않아도 된다는 사실에 유의해주세요.

입력

자세한 입력 형식은, 원문을 확인해주세요.

$1 \le N \le 60$은 정점의 수를 나타냅니다.

$0 \le M \le N(N-1)/2$은 간선의 수를 나타냅니다.

$0 \le K \le 15$는 이동 수를 나타냅니다.

$1 \le U_k, V_k \le N$, 은 $U_k$와 $V_k$를 잇는 간선이 있다는 것을 의미하고, $U_k \ne V_k$입니다.

두 정점 사이에 간선은 최대 하나 존재합니다.

그래프가 연결되었다고 가정해서는 안됩니다

출력

첫 번째 줄에 답을 출력하세요.

개행 문자를 출력해주세요.

답이 32비트 정수형에는 들어가지 않지만, 64비트 정수형에는 들어갈 것입니다.

풀이

힌트 1

정점의 가중치가 $2^k$와 관련된 꼴입니다. 총 가중치 순으로 방문하는 정점을 나열하면 어떻게 될까요?

힌트 2

정점 목록이 정해졌을 때, 이 정점들을 모두 방문할 수 있는지에 대한 판단을 할 수 있을까요? $K$가 작다는 점에 유의해주세요.

풀이

$2^k > 2^k-1 = 2^{k-1} + 2^{k-2} + \cdots + 2^1 + 2^0$ 이기 때문에, $k-1, \cdots, 1$번 정점을 모두 방문하는 것보다, $k$번 정점을 방문하는 것이 이득입니다. 그렇기 때문에, $1, \cdots, k-1$번 정점을 방문할지 아닐지의 여부가 정해져 있을 때는, $k$번 정점을 방문할지의 여부를 따져서, 방문할 수 있다면 방문하는 것이 항상 답을 더 크게 만들 수 있습니다.

답을 정해놓고 탐색을 할 때, 비트를 하나씩 결정하는 것과 비슷한 방법입니다.

정점 목록이 정해졌을 때, 이 정점들을 모두 방문할 수 있는지 여부는, 흔한 외판원 문제로 풀 수 있습니다.

$D_{i, j}$를 현재까지 방문한 정점들의 목록의 비트마스크를 $i$, 마지막으로 방문한 정점을 $j$라고 할 때, 이미 방문하지 않은 정점 $k$를 잡아서 $D_{i \uplus (1 \ll k), k}$의 가중치를 $D_{i, j}$에다 $j$부터 $k$까지의 거리를 합한 것 등으로 구할 수 있습니다. 이 경우에 확인할 정점이 $x$ 개라면 $O(x^2 \times 2^x)$의 시간이 들게 됩니다.

시간 복잡도는 모든 정점 간의 거리를 구하는 것과, 정점을 방문할 수 있는지 판단을 총 $N$번 하는 시간이 됩니다. 여기서, 방문한 정점의 목록은 $K$개를 넘을 수 없기 때문에, 총 $O(N(M+K \times 2^K))$ 정도의 시간이 들게 됩니다.

 

코드: https://yukicoder.me/submissions/735888