위상 정렬

위상 정렬 문제인 백준 그래프 수정 문제을 풀면서 했던 고민을 작성합니다.

해당 문제에서의 핵심은

• V1 -> V2 간선이 있을경우 V1 > V2 이다
• 1 ~ N 각각의 노드가 바뀐 숫자를 순차적으로 출력할 때 결과값이 사전식 순서에서 가장 앞에 와야한다.

위상정렬을 수행하고 같은 위상에서의 가장 왼쪽 노드의 번호를 부여할 수 있는 숫자 중 가장 낮은 숫자로 부여했다.

결과는 틀렸다.

반례로써

4
0011
0000
0000
0100

의 결과는 1342가 나와야 하지만 나의 풀이로는 1423이 나왔다.

이유를 생각해봤는데 최종적으로 내린 결론은 탐욕 알고리즘과 같이 매번 최선의 경우를 선택해도 최선의 결과가 나올 수 없다 였다.

나의 풀이는 위상정렬을 수행하고, 각 위상에서의 최선의 선택을 반복함으로서 결과를 도출해냈지만 그렇지 않은 경우가 발생했기 때문이다.

특히 아래 사진의 중앙부분에 파란선으로 그린 그래프 두가지가 나오는데
내가 도출한 그래프와, 반례의 그래프를 살펴보면 문제에서 주어진 조건을 모두 만족한다.

나는 q를 사용해서 구현했기에 최소힙으로 구현한 우선순위큐를 사용하면 되지 않을까 생각했지만 결과는 또 실패했다.

위상정렬 수행시의 주의점

위상정렬은 그래프에 존재하는 각 노드의 진입차수 (indegree)를 기준으로 정렬을 수행한다.
진입차수가 0이면 그보다 앞에 존재하는 노드는 있을 수 없다는 점을 기준으로 정렬을 수행하는데

이를 일반적인 글자를 사전식으로 정렬하는 것에 적용을 해보겠다.

여기 ac, ab, ba 라는 글자가 있다.

1번: 첫번째 글자를 기준으로 정렬한 후 두번째 글자 기준으로 정렬한다.
2번: 두번째 글자를 기준으로 정렬한 후 첫번째 글자 기준으로 정렬한다.

1번의 경우 정렬이 제대로 수행되지 않는다. 왜냐하면 가장 높은 우선순위인 첫번째 글자를 기준으로 정렬을 수행한 뒤, 두번째 우선순위인 두번째 글자를 기준으로 정렬할 때 이전에 수행했던 정렬 내용이 깨지기 때문이다.

만약 각 글자별로 위상을 나눠서 수행한다면 정상적으로 수행할 수 있겠지만, 그렇다면 모든 글자를 쪼개서 하나하나 정렬을 수행해야하는 번거로움이 생긴다.

여기서 방법이 생기는데 낮은 우선순위의 기준부터 정렬을 수행한다 이다.

2번의 방법을 통해서 2번째 글자를 기준으로 정렬을 한뒤, 첫번째 글자를 기준으로 정렬을 수행하게 되면 내가 원하는 사전식 우선순위로 정렬이 수행된다.

즉 위상정렬을 내가 원하는 방식으로 사용하기 위해서는 가장 낮은 우선순위의 기준부터 높은 우선순위까지 순차적으로 정렬을 수행해야 한다는 결론이 나온다.

어떻게 보면 이미 알려진 내용이기도 하고 의미가 있는 내용인가 생각이 들지만 나에겐 의미깊었던 결과였다.

추가내용

ac, ab, ba를 우선순위 순서에 관계없이 각각 정렬할 때의 문제점우선순위가 낮은 것 부터 차츰 정렬해 나가는게 모든 정렬 알고리즘의 핵심이다 라는 말을 들었다.

위상정렬 만의 문제는 아니라는 뜻이다.

생각해보니 당연한 말이였다. 버블정렬, 선택정렬, 힙정렬, 합병정렬 같은 정수값들을 정렬하는데는 우선순위가 값의 비교 밖에 없으니 이런부분을 생각하지 못했다.

모르겠다.

처음 시작은 어떤 조건을 확인했을 때 그래프 수정 문제를 역방향으로 풀어야 할까 라는 부분을 캐치하고 싶었는데 첫 의도와 많이 빗나갔다는 느낌이 들었다.

현재로써 정리하기로는 이전과 동일하게 낮은 우선순위의 요소부터 정렬한다 와 매번의 최선의 선택이 항상 최선의 결과를 도출하지는 않는다 두가지 밖에 떠오르지 않는다.

오늘 하루는 내 인생에서 꽤 의미깊은날이 되지 않았나 싶다.