거인의 어깨 위에 올라서기

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

1865번: 웜홀

 

문제에 대한 스포일러가 있다. 원하지 않는 분은 뒤로가기를 누르시길.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

보자마자 '벨만-포드 알고리즘인가?'라고 생각했다. 해당 알고리즘에 속하는 문제를 풀어본 적은 없지만, 다익스트라를 배울 때 '간선의 가중치가 음수인 경우에는 벨만-포드라는 알고리즘을 써야 한다'는 이야기를 얼핏 들었던 기억이 나서다.

 

벨만-포드 알고리즘의 구현을 훑어보고 보다 쉬운 문제를 해결한 뒤 웜홀 문제에 도전했다. 박살났다. 내 구현은 O(V^2 * E) 정도 되는 알고리즘(여기서 V는 정점, E는 간선의 개수를 말한다)이었는데, 당장 떠올릴 수 있는 사소한 최적화를 해봐도 시간 초과를 극복할 수 없었다.

 

결국 간선의 숫자에 비해 정점의 숫자가 작다(V < E)는 점을 이용해서 플로이드-워셜(O(V^3))로 문제를 해결하긴 했지만 찝찝했다. 내가 벨만-포드 알고리즘을 이해한 게 아니라 그 특정 구현만을 암기하고 있다는 느낌을 받았다.

 

벨만-포드 알고리즘의 중요한 컨셉은 '이미 갱신된 최소 비용이 한 번 더 갱신되면 음의 가중치를 갖는 사이클이 존재한다'는 것이다. 그렇다면 '갱신된 최소 비용'이라는 것은 어떻게 보장하는가? 잘 알려진 O(V*E) 시간복잡도를 갖는 풀이에서는 '음의 가중치를 갖는 사이클이 없다면, 최소 비용을 갖는 경로에서 시작점과 도착점을 잇는 간선의 개수는 V-1을 넘을 수 없다'라는 명제(의 대우 명제)를 구현했다.

 

더… 잘할 수 있을 것 같았다. 힙 자료구조를 이용한 다익스트라의 구현이 자꾸 아른거렸다. 벨만-포드에서도 혹시? 하지만 그게 된다면 다른 블로그 등지에서 그 풀이를 기술하지 않았을 리가 없다. 나는 생각을 포기하고 다른 사람 풀이나 탐방하기로 했다.

 

많은 사람들이 '마이너스 사이클이 하나 이상 존재하는가'라는 질문을 "결과적으로" 구현한 것 같았다. 최소 비용을 저장해두는 배열을 굳이 inf로 초기화하거나, 해당 배열의 0번째 혹은 1번째 인덱스의 값을(그것이 시작 위치라고 생각한 모양이다) 0으로 초기화하는 등 문제의 요구사항을 오해하고 있다는 느낌을 받았다. 실제로 그런 풀이들은 최소 비용 배열을 -INF 따위로 초기화해도 정답을 찾을 수 있다. O(V*E)의 풀이였지만 이 문제에서만 통용될 것 같아서 마음에 들지 않았다.(물론 문제에서 요구하는 바가 그것이긴 하다)

 

그러다 우연히 어떤 풀이를 만났다. 힙을 이용해서 마이너스 사이클의 존재를 판별하는 알고리즘이었다. 시간복잡도는 O(V*ElogE). 하지만 적절한 가지치기를 함으로써 위에서 언급한 O(V*E) 풀이보다 더 빠른 속도로 문제를 해결한다.

 

그 구현은 정말로 간결하지만 내 앎의 범위에서 그렇게 멀지 않았다. 나도 어쩌면 그 풀이에 닿았을지도 모른다. 물론 그것은 가정법이고, 현실의 나는 개척자가 아니라 다른 사람의 풀이를 염탐하여 지식을 얻은 사람에 불과했지만.

 

그렇지만, 그걸로 좋다고 생각했다. 만약 내가 PS 그 자체를 목적으로 공부하는 사람이었더라도 마찬가지였을 것이다. 혼자서 해결했다면 칭찬 받아 마땅한 일이다. 하지만 그뿐이다. 중요한 것은 비슷한 문제를 다시 마주했을 때 내가 유의미하게 성장했느냐다. 나 혼자 해결했더라도 성장하지 않았더라면 그 시간은 그저 즐거웠을 뿐이므로.

 

나는 혼자서 머리를 박는 시간이 너무나도 길었다. 아직도 철이 덜 든 것이다. 무엇이 중요한지를 모르고 그저 즐거움만을 탐한다. 퍼즐 미스터리를 푸는 거지, 아이처럼.

 

당연하지만 베끼는 것 자체가 효율적이진 않다. 그 발상을 하기 위해 필요한 숙련도가 뭔지, 그걸 어떻게 훈련할 것인지에 대해서 고민하는 시간이 필요하다. 베끼는 것을 넘어서 체화하는 노력이 요구된다. 그렇게 제것으로 만들었다면 그걸로 좋다. 우리는 적정한 기준 위에서 다른 사람의 지식을 탐하기를 그치지 말아야 한다. 거인의 어깨 위에 서는 것을 주저하지 말아야 한다.