BOJ-백준 2252번 줄 세우기 C++ 문제 풀이 입니다.
링크 : https://www.acmicpc.net/problem/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를 출력합니다.
::
'✅ 문제풀이' 카테고리의 다른 글
BOJ-백준 1948번 임계경로 C++ (0) | 2021.10.21 |
---|---|
BOJ-백준 1516번 게임 개발 C++ (0) | 2021.10.21 |
BOJ-백준 14852번 타일 채우기 3 C++ (0) | 2021.10.18 |
BOJ-백준 2133번 타일 채우기 C++ (0) | 2021.10.18 |
BOJ-백준 11727번 2xn 타일링 2 C++ (0) | 2021.10.17 |