문제 정의
특정 개수의 문자열을 받고, 그 정보를 바탕으로 알파벳 사전 순서를 결정하는 문제이다. 그래프와는 관련이 없어 보이는 문제이지만, 위상 정렬의 특성을 확인하면 문제를 해결할 수 있다.
위상 정렬은 의존성을 가진 그래프, 즉 순서를 가진 그래프를 순서에 모순이 생기지 않도록 정렬해 주는 특성을 가지고 있다. 알파벳 사전 순서를 예로 들면 d는 반드시 a,b,c 뒤에 와야 한다는 의존성을 가지고 있다. 따라서 알파벳 순서로 정렬하는 데 위상 정렬을 활용하면 순서에 모순이 생기지 않게끔 정렬하는 것이 가능해진다.
문제 풀이
위상 정렬을 활용해 위 문제를 해결하기 위해서는 먼저 위상 정렬할 그래프를 만들어야 한다. 의존성을 가진 그래프를 만들기 위해 주어진 문자열에 대해 서로 비교하면서 다른 문자가 등장했을 때 그 두 문자가 순서의 차이를 가져온 문자이므로 두 문자에 대해 엣지를 만들어 준다. 순서가 늦은 문자가 빠른 문자에 대해 의존성을 가져야 하므로 늦은 문자에서 빠른 문자 방향으로 엣지를 만들어 준다.
이렇게 모든 의존성을 나타낸 그래프를 만들어준 다음 위상 정렬을 실행하면, 정렬된 형태의 문자열을 얻을 수 있다.
그래프를 만들 때 모든 단어끼리 n^2만큼 비교할 필요가 없는데, 이는 a,b,c 세 단어를 비교한다고 했을 때 인접한 단어끼리만 비교해도 모든 정보를 얻을 수 있기 때문이다. a와 b, b와 c의 비교를 통한 정보만으로도 a와 c를 비교했을 때의 정보를 얻을 수 있다.
1,2,3 의 크기를 비교 할 때 1과 3을 직접 비교하지 않아도 3이 더 크다는 정보는 자동으로 알 수 있는 것과 같다.
느낀점
문제 풀이에 핵심적인 부분은 위상 정렬의 활용이다. 문제가 요구하는 사항이 의존성을 가진 관계를 알려 주고 그 정보를 바탕으로 정렬을 하라는 것일 때 위상 정렬은 유용하게 사용될 수 있다.
