0x1A. 위상정렬 - 백준 2252번
바킹독 0x15강 - 위상정렬Permalink
오늘은 바킹독의 위상정렬 공부
위상정렬 알고리즘Permalink
2252번: 줄세우기Permalink
알고리즘Permalink
- vertex의 indegree 값을 넣은 indegree table →
vector<int>로 생성- index == B 인 애들만 +1
- indegree가 0인 vertex의 index을 queue 로 이동 →
queue<int>필요 - queue에서 하나씩 꺼내면서 결과 테이블로 이동 →
vector<int>필요 - 꺼낸 vertex와 이어진 vertex의 indegree를 -1 = 끊어졌기 때문에
- indegree가 0이 되면(독립적) queue 로 이동
- queue가 빌때까지 3,4 번을 반복
주의Permalink
- 꺼낸 vertex와 이어진 vertex를 찾기 위해서 경로를 알 수 있는 변수가 필요 →
map <int, vector<int> >사용 - 한가지 vertex에 2개 이상이 연결 된 경우 (1→3 , 1→2) : map의 vector를 사용
- chatGPT:
unordered_map>map,unordered_map쓰는게 성능이 높다. vector<vector> 도 가능
코드Permalink
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int main()
{
int N,M;
cin >> N >> M;
vector<int> vec(N+1, 0);
map <int, vector<int> > map;
vector<int> result;
for(int i=0;i<M;i++) {
int A, B;
cin >> A >> B;
map[A].push_back(B);
vec[B]++;
}
queue<int> que;
for(int i=1;i<=N;i++) {
if(vec[i] == 0) {
que.push(i);
}
}
while(!que.empty()){
// cout << que.front() << "\n";
int value = que.front();
que.pop();
result.push_back(value);
while(map[value].size()>0) {
int val = map[value].back();
map[value].pop_back();
vec[val]--;
if(vec[val] == 0) {
que.push(val);
}
}
}
for(int i=0;i<result.size();i++) {
cout << result[i] << " ";
}
}