위상정렬이란?
위상 정렬은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. - 위키백과-
뭐라는거야... 하나도 이해안된다.
그래서 간단하게 설명하면 순서가 정해져있는 것들을 차례대로 정렬하는 것이다.
이렇게 말해도 이해가 안될거다.
간단한 예시를 들어보자.
당신이 밖에서 일정을 마치고 집으로 돌아왔다. 집으로 도착하자마자 샤워부터 해야한다. 그 후 밥을 먹고 잘 수 도 있고 바로 잘 수도 있다. 이때 순서를 구해보자.
아래와 같은 순서가 나온다.
씻기 - 밥먹기 - 자기
이게 뭔 위상정렬이냐 생각할 수도 있다. 하지만, 원리를 설명하고 다시 보자
선행되어야 하는 작업 -> 해당 작업 이후에 할 수 있는 작업
이렇게 나타냈을 떄 위상정렬에서는 자신에게 향해지는 화살표가 먼저 0개가 되는 순서대로 정렬된다.
씻기 -> 밥먹기
씻기 -> 자기
밥먹기 -> 자기
이렇게 있을 경우 자신에게 향하는 화살표의 수는 아래와 같다.
씻기 : 0개
밥먹기 : 1개
자기 : 2개
이때 0개인 씻기가 먼저 정렬된다면, 씻기가 가리키던 화살표는 사라진다.
그렇게 밥먹기 0개, 자기 1개 가 되기 때문에 씻기, 밥먹기, 자기 라는 순서대로 위상정렬이 된다.
아래 예시와 함께 보겠다
방향성을 찾아보자
5 -> 11
7 -> 11
7 -> 8
3 -> 8
3 -> 10
8 -> 9
11 -> 2
11 -> 9
11 -> 10
그렇다면 자신에게 향하는 화살표의 수를 체크해보자
0개 : 5, 7, 3
1개 : 2
2개 : 11, 8, 9, 10
그럼 0개에 해당하는 5, 7, 3을 순서대로 queue에 넣는다.
맨 앞에서 하나씩 빼며 화살표의 수를 없애보자.
5를 뺐을때는 화살표가 0개인 값이 생기지 않지만, 7까지 뺐을 경우 11을 가리키는 화살표가 없어진다.
그렇기 때문에 11 또한 queue에 넣어준다.
3을 뺐을때도 8을 가리키는 화살표가 0개가 되기 때문에 queue에 8을 넣어준다.
그 다음은 계속 반복해준다.
11을 뻈을때 2를 가리키는게 0개가 되고, 10 또한 0개가 된다. 그래서 2와 10을 queue에 넣어준다.
queue에서 8을 빼면 9를 가리키는게 0개가 되기 때문에 queue에 넣어준다.
지금까지 넣었던 순서대로 5 7 3 11 8 2 10 9 이 나오게 된다
이때 나는 무조건 왼쪽 위가 먼저라고 가정하고 문제를 풀어 위와 같은 답이 나왔지만, 숫자가 작은 것을 우선으로 했거나, 우측 상단을 우선으로 했다면 순서가 약간은 변화할 수 있다.
이렇듯 위상정렬을 적용했을 때에도 기준에 따라 여러개의 값이 나올 수 있다.
이것을 적용한 문제가 백준의 2252번 이다.
적용해서 문제를 풀었고, 확실히 유용했다.
조만간 문제 풀이 정리해서 글 쓰고 아래 링크 남기겠다.