엘리스 알고리즘 코드 챌린지, 예선 6일 차 문제

강의는 BFS, 다익스트라이다.

강의와 문제는 큰 연관이 있다. 다익스트라를 쓰면 된다.

문제는 빨간 선과 파란 선(링크 없음, 골1?, 풀이 3시간15분)이고 "정점의 개수 N이 주어지고 0 혹은 1을 원소로 갖는 길이 N-1의 배열 colors가 주어진다. 차례마다 2개의 서로 연결되지 않은 정점 u와 v를 고른 뒤, u가 포함된 연결 요소 내의 모든 정점들로부터 v가 포함된 연결 요소 내의 모든 정점들에 간선을 잇는다. 이때 2<=N<=30이고 간선의 색은 0이면 빨간 색, 1이면 파란 색이고 k번째 차례에는 colors[k]를 사용해야 한다. 이때 사용한 빨간 간선의 개수의 최솟값을 출력하라."이다.

풀이는 다익스트라를 쓰면 된다.
첫 시도는 그룹의 크기를 담은 배열과 그리디 알고리즘을 이용하였다. 파랑일 때는 그룹의 크기가 가장 큰 두 그룹을 묶고 빨강일 때는 그룹의 크기가 가장 작은 두 그룹을 묶었다. min-max-heap을 쓰면 좋았겠지만 그냥 배열 순회로 찾았다. 그리디로 못 푸는 반례가 있는 듯하고 틀렸다. 크루스칼 알고리즘에 이끌려 유니온파인드 알고리즘도 쓰긴 했는데 중간부터 쓸모없는 걸 알아챘다.
두 번째 시도는 브루트포스를 이용하였다. 시간 초과가 났다.
세 번째 시도는 다익스트라를 이용하였고 정답 판정을 받았다.

# n = 5
#         [1,1,1,1,1]
#              |
#          [1,1,1,2]
#          /       \
#    [1,2,2]       [1,1,3]
#     /   \         /   \
#  [2,3] [1,4]   [2,3] [1,4]
#              |
#             ...
#              |
#             [5]

브루트포스는 위와 같이 진행되었다. 여기서 잘 보면 [2, 3], [1, 4]는 중복 방문되는 정점이라는 것을 알 수 있다. 한 경로로 낮은 비용으로 해당 정점에 갔더라도 다른 경로로 높은 비용으로 다시 해당 정점에 도착 후 동일할 예정인 미래의 경로를 진행하게 되고 이 과정에서 비효율이 발생한다. 해답이자 세 번째 시도는 이렇게 그래프를 정점으로 변환 후 다익스트라 알고리즘을 통해 효율적으로 최단 경로를 탐색하는 것이다. 여기서 다시 첫 방법인 그리디 알고리즘을 떠올려보면 모든 경로를 파악하지 않고 딱 한 경로만 그리디하게 탐색한 셈이고 이 과정에서 놓치는 최적 경로가 있는 듯하다. 발상이 어려운 것이지 다익스크라 코드와 최단 경로 증명은 자명하니 생략한다.
최대 정점의 개수를 계산하지 못해 시간 초과가 날까봐 걱정이 되었는데 다행히 그러지는 않았다. n=30일 때도 정점의 개수는 5604개밖에 되지 않고 바로 위 계층의 정점 혹은 바로 밑 계층의 정점과만 연결되니 E는 매우 작을 것이다. 수식화하면 정점의 개수는 partition_funtion(n)이고 수식은 복잡하니까 위키피디아를 참고하라. 주의해야 할 구체적인 구현을 예시를 들어가며 말하자면, 정점 [1, 2, 2]를 [0, 1, 2, 0, 0, 0]의 계수 배열로 변환하였고, 이를 튜플로 변환 후 해시화하여 dists 딕셔너리에 넣었고, [0, 1, 2, 0, 0, 0]로부터 도달가능한 다음 정점들은 nC2를 돌리며 계수의 수정을 통해 낮은 시간복잡도로 찾을 수 있다. 순열과 조합은 재귀를 통해 구현하는 게 일반적이지만 이번에는 2로 개수가 적기 때문에 이중반복문을 통해 구현하였다.

n = int(input())
c = list(map(int,input().split()))
dp = dict()
dp[tuple([1] * n)] = 0
queue = [tuple([1] * n)]
queueIndex = 0
while len(queue) > queueIndex:
    v = queue[queueIndex]
    queueIndex += 1
    for i in range(len(v)):
        for j in range(i + 1, len(v)):
            u = []
            for k in range(len(v)):
                if k == j:
                    u[i] += v[k]
                else:
                    u.append(v[k])
            u = tuple(sorted(u))
            if u not in dp:
                dp[u] = dp[v] + v[i] * v[j] * (1 - c[n - len(v)])
                queue.append(u)
            else:
                dp[u] = min(dp[u], dp[v] + v[i] * v[j] * (1 - c[n - len(v)]))
print(dp[(n,)])

솔루션은 위와 같다. 주석도 없고 변수명도 i, j, k, u, v로 알아보기 힘들지만 visited 대신 dp(=다익스트라의 dists)를 사용하는 bfs로 보인다. 다익스트라에서 최솟값을 우선순위큐에서 빼지 않고 아무거나 빼도 최단 경로가 보장이 되는데 그런 구현과 기본적으로 동일하다. 단지 시간복잡도가 보장이 되지 않을 뿐이다. N=30, 랜덤 colors 입력에서 나의 풀이가 170ms, 솔루션이 1000ms가 소요되었다.

갑자기 난도가 급상승했다. 현재까지 만점자 중 50번째로 빨리 푼 사람이 14:13분, 100번째로 빨리 푼 사람이 21:05분에 풀었다. 대충 추세를 보면 당일 내에 푼 사람은 130명 정도가 될 듯하다.