위상 정렬

위상정렬

순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정하기 위해 사용하는 알고리즘

 

순서가 정해져있는 예시

 

위상정렬을 통해 여러개의 순서를 조건에 부합하는 일직선의 순서로 만든다.

배고픔 -> 돈벌기-> 배달 앱 설치하기 -> 배달시킬 음식 고르기 -> 주문서 작성하기 -> 결제하기 -> 배달 완료

 

위상정렬은 다른 수서의 답 또한 존재할 수 있다. 

위상정렬은 사이클이 존재하지않는 그래프(DAG)에만 적용가능하다.

 

위상정렬은 

현재 그래프가 위상정렬이 가능한지 판별가능

위상정렬이 가능하다면 그 결과는 무엇인지

와 같은 두가지의 해결책을 낸다.

 

위상정렬은 스택과 큐를 이용한 두가지의 방식이 존재한다.

 

큐를 이용한 방식

1. 진입차수가 0인 정점을 큐에 삽입한다.

 -> 특정한 노드로 들어오는 노드의 개수 = 진입 차수 

2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.

3. 간선 제거 이후에 진입차수가 0이된 정점을 큐에  삽입한다.

4. 큐가 빌 때 가지 2번~3번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문 했다면 큐에서 꺼낸 순서가 위상 정렬의 결과입니다.

 

과정을 수행해보겠습니다.

 

첫번째로 1의 진입차수가 0이므로 큐에 삽입한다.

 

그리고 간선을 제거해줍니다.

정점	1	2	3	4	5	6	7
진입차수	0	0	1	1	0	2	1

간선을 제거하면 위와같이 표가 변하게 됩니다.

 

 

 

두번째로 진입차수가 0이된 정점들을 다시 큐에 삽입합니다.

그리고 다시 간선을 제거해줍니다.

 

그러면 아래와 같이 값이 변하게 된다.

정점	1	2	3	4	5	6	7
진입차수	0	0	0	1	0	2	1

이때 3이 진입차수가 0이 되었으니까 큐에 3을 넣어줍니다,

 

그리고 다시 큐에서 5를 꺼내 5의 간선을 모두 제거해줍니다,

정점	1	2	3	4	5	6	7
진입차수	0	0	0	1	0	1	1

여기서 새롭게 진입차수가 0인게 발견되지 않으므로 넘어간다.

 

큐에서 3을 꺼내서 3의 간선을 제거해준다.

정점	1	2	3	4	5	6	7
진입차수	0	0	0	0	0	1	1

4의 진입차수가 0이 되었으므로 4를 큐에 넣어준다.

 

 

이러한 방식으로 모두 큐를 지나가면 정답은 큐에서 빼낸 순서가 됩니다.

 

 

코드를 구현해보겠습니다.

 

var n=7
var node =[
    [1,2],
    [1,5],
    [2,3],
    [3,4],
    [4,6],
    [5,6],
    [6,7]
]
let answer = [];
let graph = Array.from(Array(n + 1), () => Array().fill(0));//그래프 표
let indegrees = Array(n + 1).fill(0);//진입차수
let queue = [];

//주어진 연결된 노드를 인덱스번호마다 넣고 간선수 그 수에 맞게 또한 저장한다
for (let [a, b] of node) {
    graph[a].push(b); //a번에서 b번 노드로 갔다는 의미
    indegrees[b]++; //b번노드의 진입차수를 증가시킨다.
}

//진입차수가 0인 것을 찾아 queue에 넣는다. 모든 노드를 검사함
//0부터하지않는 이유는 0번인덱스는 제외했다.
for (let i = 1; i < n + 1; i++) {
    if (indegrees[i]==0) queue.push(i);//해당 노드 번호를 queue에 삽입한다.
}
if(queue.length==0){
    	console.log("사이클이 발생했습니다.");
}
while (queue.length) {
    //만약 사이클이 발생하지 않는다면 큐에 맨 앞의 값을 빼서 x에 넣는다.
    var x = queue.shift();
    //큐에서 빼낸 순서가 답이므로 answer에 넣어준다.
    answer.push(x);
    for (let next of graph[x]) {//큐에서 빼낸 x에 연결되어있는 모든 정점을 모두 순회한다.
      indegrees[next]--; //x에 연결되어있던 간선을 제거한다.
      console.log(indegrees)
      if (indegrees[next]==0) queue.push(next);//만약 간선이 0이면 큐에 삽입한다.
    }

	
}
console.log(answer)

 

예제1.

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

2252번: 줄 세우기

줄 세우기 스페셜 저지

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

40013

23303

15454

56.538%

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1 복사

3 2
1 3
2 3

예제 출력 1 복사

1 2 3

예제 입력 2 복사

4 2
4 2
3 1

예제 출력 2 복사

4 2 3 1

 

 

 

 

---

 

 

 

예제 2.

https://school.programmers.co.kr/learn/courses/30/lessons/76503

프로그래머스

 

모두 0으로 만들기

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

---

제한사항

• a의 길이는 2 이상 300,000 이하입니다.
  • a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
  • a[i]는 i번 정점의 가중치를 의미합니다.
• edges의 행의 개수는 (a의 길이 - 1)입니다.
  • edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
  • edges가 나타내는 그래프는 항상 트리로 주어집니다.

---

입출력 예aedgesresult

[-5,0,2,1,2]	[[0,1],[3,4],[2,3],[0,3]]	9
[0,1,0]	[[0,1],[1,2]]	-1

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 트리의 모든 정점의 가중치를 0으로 만드는 과정을 나타낸 것입니다.

1. 2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
2. 3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3. 0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)

• 모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.

입출력 예 #2

• 주어진 트리는 모든 정점의 가중치를 0으로 만드는 것이 불가능하므로, -1을 return 해야 합니다.

 

bottom-up DFS방식이다.

즉 차수가 없는 자식노드까지 가서 밑에서부터 시작을 해야한다.

그래서 스택을 이용했다.

원리는

1. 0부터시작 → [0,-1] ⇒ 임의의 최상위노드다. [자식노드,부모노드]
2. 스택을 빼는데 만약에 방문을 하지않았다면 다시 스택에 넣고, 방문표시를 해준다.
3. 현재 진행중인 노드에 연결된 노드 중 방문하지 않은 노드를 스택에 모두 넣는다.
4. 즉 부모노드부터 아래로 방문을 표시해주면서 스택에 다시넣고, 차수가 없는 자식 노드까지 가는 것이다.(leaf node)
5. 왜냐하면 방문을 하지 않은 노드가 없으면 모두 방문을 해서 leaf 노드임을 증명하는 것이다.
6. 그렇게 leaf node에 도착하면
7. 스택을 빼면서 부모 노드들은 방문을 했으니까 이때 가중치들을 모두 남김없이 빼서 부모에게 준다. 그리고 형제노드가 있는지 살펴야 하므로 다시 bottom up을 수행한다.
8. 이런 방식이면 최상위 노드까지 갔을 때 모두 빼질 것이다.
9. 근데 이게 DFS이므로 leaft노드를 찾는 것도 한쪽만 찾는 것이다.
10. 그래서 다시 최상위 노드까지가도 또 다시 leaf노드를 찾으러 간다.(자식노드가 더 있을 수 있으니까)
11. 그래서 continue로 방문을 했던 노드들이 스택에서 나오면 스택을 넣는것을 멈추면서 점점 연결되었다던 노드들이 사라지는 것이다.

function solution(a, edges) {
    const tree = new Array(a.length).fill().map(_ => []);
    //방향그래프가아니고 서로 연결된거니까 두번 push한다.
    for(const [u, v] of edges) {
        tree[u].push(v);
        tree[v].push(u);
    }
    const stack = [ [0,-1] ];//0부터 시작해서 leaf 노드까지 내려갈 것이다.
    const visit = new Array(a.length).fill(false);
    let answer = 0n;

    while(stack.length) {
      //0부터 시작해서 leaf 노드까지 내려갈 것이다.
      const [start, parent] = stack.pop();

      //1.방문안했으면 pop했던거 도로 다시 집어넣음

      //6.만약 방문을 했다고 뜬다면 이제 leaf node에서 올라오는 중인 것이다.
      //6.그러면 자식노드의 a값을 빼서 부모한테 준다.
      //6.그리고 그만큼 answer++한다.
      if(visit[start]) {
          a[parent] += a[start];
          answer += BigInt(Math.abs(a[start]));
          continue;
      }

      //2.도로 다시 집어 넣고 이제 방문했다고 표시해줌
      //2.이렇게 하는 이유는 leaf node부터 DFS를 시작하기 위해서다.(차수가 0인) - 맨아래 노드
      //2.즉 bottom up 방식으로 DFS를 수행하는것이다.
      stack.push([start, parent]);
      visit[start] = true;

      //3.방문 표시 후에 방문한 노드의 연결된 노드들을 모두 스택에 넣는다.
      //3. 이는 자식노드들을 뜻한다.

      //5.이렇게 반복하다가 연결된 노드중에 방문안한 노드가 이제 더이상 없다고 뜰 때가 온다.
      //5. 그때가 현재 leaf node임을 뜻한다.
      //5.만약 leaf node인 즉 자식이 없는 노드에 오게되면
      //5.이제 방문을 안한 노드(자식)이 없기 때문에 스택을 넣지 않는다.

        for(const next of tree[start]) {
            if(!visit[next]) { //4.연결된것중에 방문 안한것들 스택에 넣음
                stack.push([next, start]);
            }
        }
    }

    return a[0] ? -1 : answer; 
}

 

출처

https://blog.naver.com/ndb796/221240353788

28. 위상 정렬 기초 문제풀이

https://velog.io/@song961003/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AA%A8%EB%91%90-0%EC%9C%BC%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-JS

프로그래머스: 모두 0으로 만들기 [JS]