BOJ-백준 2252번 줄 세우기 C++

BOJ-백준 2252번 줄 세우기 C++ 문제 풀이 입니다.

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

2252번: 줄 세우기

 

 

 

 

✅ C++ 정답 코드 입니다. 더보기 클릭!

#include <iostream>
#include <vector>
#include <queue>

#define MAX 32001

using namespace std;

vector<int> compare[MAX];
int inDegree[MAX];


void topologySort(int n){
  int result[MAX];
  queue<int> q;
  for(int i=1; i <= n; i ++){
    if(inDegree[i]==0) q.push(i);
  }
  for(int i=1; i <=n; i++){
    if(q.empty()){
      //cout<<"사이클이 발생"<<endl;
      return;
    }
    int x = q.front();
    q.pop();
    result[i] = x;
    for(int i= 0; i < compare[x].size(); i ++){
      int y = compare[x][i]; 
      if(--inDegree[y] == 0)
        q.push(y);
    }
  }
  for(int i =1; i<=n; i++) {
    printf("%d ", result[i]);
  }
}


int main() {
  int n; // 학생 수
  int m; // 키를 비교한 횟수
  cin >> n;
  cin >> m;
  for(int i=0; i < m; i++){
    int num1, num2;
    scanf("%d %d",&num1, &num2);
    compare[num1].push_back(num2);
    inDegree[num2]++;
  }
  topologySort(n);

}

 

📌 해설

 

위상정렬을 수행하여 학생들의 키를 순서대로 출력하는 문제입니다. 위상 정렬은 순서가 정해져 있는 작업에 대해 순서를 탐색하는 알고리즘 입니다. 

 

#include <iostream>
#include <vector>
#include <queue>

#define MAX 32001

using namespace std;

vector<int> compare[MAX];
int inDegree[MAX];

1. 필요한 변수들을 선언합니다. compare과 inDegree는 모두 전역으로 선언했기 때문에 0으로 초기화 됩니다. 

compare에는 학생들의 키를 비교한 정보를 그래프로 저장합니다.

inDegree에는 진입 차수를 저장합니다. 

학생 수는 최대 32,000명 까지 입력될 수 있으므로 최댓값 MAX를 define해줍니다.

 

int main() {
  int n; // 학생 수
  int m; // 키를 비교한 횟수
  cin >> n;
  cin >> m;
  for(int i=0; i < m; i++){
    int num1, num2;
    scanf("%d %d",&num1, &num2);
    compare[num1].push_back(num2);
    inDegree[num2]++;
  }
  topologySort(n);

2. main에서 모든 입력을 받은 뒤, topologySort를 수행합니다. 인자로는 학생 수를 넘겨줍니다. 

 

void topologySort(int n){
  int result[MAX];
  queue<int> q;
  for(int i=1; i <= n; i ++){
    if(inDegree[i]==0) q.push(i);
  }
  for(int i=1; i <=n; i++){
    if(q.empty()){
      //cout<<"사이클이 발생"<<endl;
      return;
    }
    int x = q.front();
    q.pop();
    result[i] = x;
    for(int i= 0; i < compare[x].size(); i ++){
      int y = compare[x][i]; 
      if(--inDegree[y] == 0)
        q.push(y);
    }
  }
  for(int i =1; i<=n; i++) {
    printf("%d ", result[i]);
  }
}

3. 위상 정렬을 수행합니다.

3-1. 큐와 위상정렬을 수행한 결과를 저장할 배열을 선언합니다. 

3-2. 진입차수가 0인 모든 노드를 큐에 삽입합니다. 

3-3. 노드 갯수(학생 수)만큼 반복하는 for문을 작성합니다. 

3-4. 큐가 비어있다면 반복을 종료합니다. (사이클이 발생)

3-5. 큐의 첫번째 원소를 꺼내 x에 저장합니다. 

3-6. 꺼내진 원소는 result에 저장됩니다. 

3-7. x 노드(학생)과 연결된(비교된) 모든 노드에 접근하도록 for 문을 작성합니다. 

   3-7.(1) x 노드에 연결된 노드를 y 로 선언합니다. 

   3-7.(2) y에 연결된 간선을 하나 제거 합니다.(--진입차수)

   3-7.(3) 만약 간선 하나가 제거한 후 진입 차수가 0이 되면(진입 되는 노드가 하나도 없게 된다면) 노드 y를 큐에 삽입합니다. 

3-8. 위 반복문이 끝나면 result를 출력합니다. 

 

 

 

 

::