[BOJ 16329] Space Station

https://www.acmicpc.net/problem/16329

16329번: Space Station

신기한 방법으로 풀어 문제를 포스팅해봅니다. 증명을 못했는데 혹시 증명법이나 관련 정리를 알고 계시면 알려주시면 감사하겠습니다.

 

크기 $n(\leq 1000)$의 트리가 주어져있을 때 root에서 시작해서 모든 에지를 한번 이상 방문하고 root로 돌아오기 위한 최소비용(=최단시간)을 구하는 문제입니다. 이상적인 경로가 존재하면 모든 에지를 한번씩만 방문하면 되어 에지 길이 총합이 답이 되겠지만 그래프가 트리로 주어져 있기 때문에 불가능합니다. 결국 모든 에지를 정확히 두번 씩 방문하고 돌아오는 것이 최단 경로가 된다는 것까지 쉽게 확인할 수 있습니다. 따라서 추가 조건이 없을 경우 (에지 길이들의 합)$\times 2$가 답이 될 것입니다.

 

여기에 이제 특별한 이동이 하나 추가 됩니다. 임의의 두 점 사이를 에지를 통하지 않고 한번에 이동하는 것입니다. 비용은 $k$로 주어져 있습니다. 이동을 하다가 아무 점에서 시전해도 되지만 시전할 수 있는 횟수가 최대 $m(\leq 1000)$번으로 제한되어 있습니다. 이 이동을 jump라 부르겠습니다. 아래와 같이 jump를 이용하면 중복되는 이동을 피할 수 있어서 효율적인 경로를 짤 수 있습니다. 하지만 jump에도 비용이 소모되기 때문에 무조건 많이 사용할수록 좋은 것은 아닙니다.

 

 

 

문제에 자연스럽게 접근해보겠습니다. jump횟수가 $x$번으로 고정되어 있는 경우의 최단경로를 생각해보겠습니다. 횟수가 고정되어 있으므로 jump비용은 신경 쓰지 않아도 됩니다.

 

최단경로는 결국 순서에 상관없이 각 에지를 몇 번씩 지났냐에 따라 결정됩니다. 따라서 각 에지를 최대한 조금만 이용해서 경로를 짜야 합니다.

한 에지를 세번 이상 이용하면 최단경로가 될 수 없다는 것은 쉽게 증명이 가능합니다. 굳이 다시 가야할일이 있다면 첫 방문에서 처리하고 가는 것이 더 효율적이기 때문입니다. 문제 조건에 의해 최소 한번은 이용해야 하므로 최단경로에서 모든 엣지는 1번 혹은 2번 이용할 것입니다. 

 

따라서 문제를 다음과 같이 바꿔서 생각할 수 있습니다. 각 에지들을 이동하는 횟수가 1 혹은 2로 정해져 있을 때 jump를 $x$번 이용하여 가능한가? 이는 한붓그리기로 잘 알려져있는 문제입니다. 홀수점(차수가 홀수인 점)이 $2x$개 이하면 jump를 x번 이하 이용하여 이동이 가능합니다.

 

그렇다면 이제 각 에지들의 이동횟수를 1 혹은 2로 정해 홀수점이 $2x$개 이하가 되도록 해야 합니다. 이때, 이동횟수가 1인 에지가 많으면 좋을 거 같고 이왕이면 길이가 긴 에지의 이동횟수가 1일수록 좋을거 같습니다.

이동횟수가 2인 에지는 각 점의 차수의 홀짝성에 영향을 주지 않습니다. 따라서 이동횟수가 1인 에지들을 살펴봐야합니다. 상황을 단순화하기 위해 이동횟수가 2인 에지를 제거하고 생각해도 무방합니다.

1인 에지들이 하나의 path로 이어져 있을 경우 양 끝점을 제외하고는 홀짝에 영향을 주지 않으며 양 끝점만 홀수가 됩니다. 따라서 홀수점이 $2x$개 이하일 경우, $x$개의 path의 합집합으로 표현할 수 있지 않을까 추측할 수 있습니다. $x$가 1인 경우 자명한 추측이며 2, 3,...인 경우를 생각해보면 충분히 합리적인 추측이라는 것을 알 수 있습니다. 이 때 path들이 서로 겹치면 안됩니다. 아래와 같이 겹치는 path 두개는 홀수점을 6개 생성하기 때문입니다.

 

이제 비용을 고려해서 어떤 에지들의 이동횟수를 1으로 정해야 최단경로가 되는지 찾아야합니다. $x$개의 path를 정해 포함된 에지들은 1, 나머지는 2로 정해줄 것입니다. 이 경우 비용은 (전체-path합)$\times 2+$(path합)=전체$times 2-(path합)이 됩니다. 따라서 길이 합이 최대가 되도록 x개의 path를 잡으면 비용이 최소가 될 것입니다.

여기서 한단계 더 생각해보면 path가 하나 추가 될때마다 path의 길이만큼 비용이 주는 대신 jump비용이 추가되는 것입니다. 따라서 추가되는 path의 길이가 jump의 비용보다 클 경우 jump를 하는 것이 이득이며 아닐 경우 손해입니다. 하지만 살짝 신경 써줘야될게 있는데 path가 $k$개에서 $k+1$로 늘어날 때 기존의 path들을 유지하는 것보다 기존 것들을 제거하고 새로운 path를 추가하는게 이득일수도 있다는 것입니다.

 

따라서 최종적으로 문제가 다음과 같이 바뀌었습니다! 서로 겹치지 않는 path를 $m$개 이하 잡아서 path의 길이 합이 최대가 되도록 해주면 됩니다. 좀 더 엄밀히 말하면, path의 개수를 $x$개라 했을 때 path길이 합의 최댓값을 $f(x)$로 정의하겠습니다. $f(x)$는 당연히 증가함수 일 것입니다. 그리고 엄밀히 증명은 못했지만 아마 볼록함수 일 것입니다. 이 때 f(x)의 기울기가 jump의 비용보다 클 때 까지, 혹은 $x$가 $m$이 될 때까지 키워주면 되는 것입니다.

 

이 부분부터는 증명을 하지 못했지만 왠지 될거 같다~해서 제출을 해보았고 AC를 받게 되었습니다.

 

처음에 $x$가 1일 때 최대경로 하나 잡는 것은 쉽게 해줄 수 있습니다. 하지만 $x=2$가 되면 난이도가 급격히 증가합니다. $x$가 1일때와 비교해서 하고 싶은데 기존의 경로를 유지하는 것이 좋지 않을 수도 있습니다. 또한 path끼리 겹치면 안된다는 조건도 붙습니다. 뭔가 maxflow찾는거처럼 접근해야 될거 같다고 생각하면서 위의 그림을 보다가 다음과 같은 생각이 들었습니다.

path가 겹치는 경우 같이 소거해버리면 뭔가 그럴듯한 그림이 그려집니다. 일반적으로 path가 많아지는 경우에도 적용이 가능할 것처럼 보입니다. 이 경우 path가 추가 될 경우 기존에 이미 사용하고 있던 edge의 경우 비용이 줄어들게 되므로 negative 비용을 주어야 합니다. 아래의 그림을 처음에 path (a+x+b)가 먼저 추가 되고 (c+(-x)+d)의 path가 추가 되어 총 (a+b+c+d)비용을 갖게 되었다고 보는 것입니다. 이 후 상황에서 x의 비용은 다시 부호가 바뀌게 됩니다.

매번 최대 경로를 찾아서 추가해주며 path에 사용 된 에지들의 비용을 반전시켜주는 것입니다. Maxflow의 정신과도 일치하고 굉장히 그럴싸합니다.

 

Negative edge를 포함한 그래프에서 최대경로를 구해주는 것이므로 살짝 껄끄럽지만 그래프가 트리이므로 dfs를 통해 $O(n)$에 구할 수 있습니다. 따라서 전체 소모되는 시간은 $O(nm)$일 것입니다.

 

실제로 이렇게 제출해서 AC를 받았습니다. 증명만 했으면 완벽했겠지만 조금 아쉽습니다.