[백준] 2623 음악프로그램(JS)

2623번: 음악프로그램

 

위상 정렬 알고리즘을 사용하는 문제이다.

 

선수 과목을 고려한 학습 순서 결정과 같은 문제일 때, 위상 정렬 알고리즘으로 풀이할 수 있다.

 

위상 정렬을 모르시는 분들을 위해 아래를 참고해주세요!

 

위상 정렬

위상 정렬은 방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬을 말한다.

https://blog.encrypted.gg/1020?category=773649

• 위상 정렬은 사이클이 존재하지 않는 방향 그래프에서만 정의된다.
• 선수 과목과 같이 가장 앞에 올 수 있는 노드를 먼저 생각해야 한다.
• 가장 앞에 오는 노드는 자신에게 들어오는 간선이 없어야 한다.
• 매 순간마다 들어오는 간선이 없는 노드를 택한다.
• 위 그림에서 가장 앞에 올 수 있는 노드는 A, C, G이다.

 

위상 정렬 알고리즘

1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다.
2. indegree가 0인 정점들을 모두 큐에 넣는다.
3. 큐에서 정점을 꺼내 위상 정렬 결과에 추가한다.
4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1씩 감소시키고, 이때 indegree가 0이 되었다면 그 정점을 큐에 추가한다.
5. 큐가 빌 때까지 3, 4번 과정을 반복한다.

위 과정을 통해 얻은 위상 정렬 결과는 A → C → G → D → B → E → F이다.

 

작성한 코드

function solution(N, M, input) {
  // 배열 graph에는 그래프의 정보를 저장한다.
  let graph = Array.from({ length: N + 1 }, () => []);
  // 배열 indegree에는 각 인덱스에 해당하는 정점으로 들어오는 간선의 개수를 저장한다.
  let indegree = Array.from({ length: N + 1 }, () => 0);
  for (let i = 0; i < M; i++) {
    let [n, ...list] = input[i];
    for (let j = 0; j < n - 1; j++) {
      graph[list[j]].push(list[j + 1]);
      indegree[list[j + 1]]++;
    }
  }
  let queue = [];
  let ans = [];
  for (let i = 1; i <= N; i++) {
  	// 각 정점에 들어오는 간선의 개수가 없는 정점을 queue 배열에 추가한다.
    if (!indegree[i]) queue.push(i);
  }
  while (queue.length) {
    let cur = queue.shift();
    // 배열 queue에 정점을 꺼내 위상 정렬 결과를 저장하는 배열 ans에 추가한다.
    ans.push(cur);
    for (let next of graph[cur]) {
      // 정점 cur과 연결된 정점의 간선의 수를 1씩 감소시킨다.
      indegree[next]--;
      // 각 정점에 들어오는 간선의 개수가 없는 정점을 queue 배열에 추가한다.
      if (!indegree[next]) queue.push(next);
    }
  }
  // 순서를 정하는 것이 불가능한 경우에는 '0'을 출력한다.
  return ans.length === N ? ans.join("\n") : 0;
}

console.log(
  solution(6, 3, [
    [3, 1, 4, 3],
    [4, 6, 2, 5, 4],
    [2, 2, 3],
  ])
);
// 6, 2, 1, 5, 4, 3
// 1, 6, 2, 5, 4, 3

 

 

바킹독님의 [실전 알고리즘] 0x1A강 - 위상 정렬 강의를 시청 후 작성한 포스트입니다.

https://blog.encrypted.gg/1020?category=773649