BOJ 14590 KUBC League (Small)

주어진 입력값으로 그래프를 만들었다.
그리고 모든 가능한 경우를 다 확인하고 그 중 최대값을 구한다고 하면...
아마도 n! 만큼의 시간이 걸릴 것이다.

그래서 dp로 접근하기로 했다.
먼저 그래프는 1번vertex부터 시작해서 1번이 이긴 vertex로, 한 vertex에서 그 vertex가 이긴 vertex로... 이렇게 단방향으로 연결되어 있는 directed graph이다.

선수의 나열은 각 선수가 달라야 하므로 방문한 vertex는 다시 방문하면 안되고, 그렇기 때문에 방문한 vertex에 대한 기록이 필요하다. 다행이 n제한이 최대 20이라, 비트마스크를 이용해 상태 dp를 이용할 수 있다.

d[node][state] = 지금까지 방문한 점이 state이고, node에서 시작해서 얻을 수 있는 선수 나열의 최대 길이

d[node][state] = Max( d[next][state | (1<<next) ) + 1

지금까지 방문하지 않은 점 next들을 방문해보면서 그 중 최대인 값을 얻으면 된다.

근데 문제가 하나 더 있다. 바로 선수 나열의 최대길이 뿐 아니라, 선수 나열이 어떤식으로 되어있는지도 구해서 출력해야 한다.

이 부분도 좀 까다로웠는데, 처음에는
nextNode[node] = node의 다음 vertex(node)
로 놓고, Max값이 갱신될 때 nextNode[node]값을 구했는데(갱신했는데), 이럴 경우 문제가 생기는 것 같다.

node와 그에 따른 여러 state의 경우의 수가 존재하는데, 정답에 해당되는 경우가 여러 개일 수 있고, 각 경우마다 nextNode[node]값이 갱신되면 정확한 경로가 나오지 않을 수 있다.

그래서 고민하다가,
nextNode[node][state] = 지금까지 방문한 점이 state일 때, node의 다음 vertex
로 놓고, 나중에 답을 출력할 때, state도 처음부터 시작하여 다음 node에 따라 변경해주면서 선수의 나열을 출력했다. 가장 안전해 보이면서도 좀 무식한? 방법같은데 다른 방법이 떠오르지 않아서... 일단 이렇게 했다.

그리고 추가로...좀 많이 틀리고, 고민을 했는데,
결정적인 이유가 바로 배열의 크기 설정에 있었다. 상태가 0 ~ (2의 20제곱 - 1) 까지 존재하기 때문에 배열에서 다 커버해 줘야 하는데, 나는 배열의 크기를 (2의 20제곱 - 1)로 잡아
0 ~ 2의 20제곱 - 2까지만 커버했고, 그래서 printf를 이용해 디버깅할 때, 도무지 이해할 수 없는 출력 결과가 나왔다. 거의 10시부터 시작해서 새벽 3시까지 고민하다가 오전에 다시 고민해서 배열의 크기 설정이 원인이란 사실을 겨우 발견했다. 감사합니다...

그리고 내 방법은 메모리와 시간 모두 매우 크게 나와서 상위권에 있는 고수님들의 코드를 보려고 한다.

풀이도 보려고 한다. : https://www.acmicpc.net/board/view/15506