방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬
하나의 그래프에서 여러개의 위상 정렬 결과가 나올 수 있다.
DAG 에서만 사용할 수 있다.
구현의 편의를 위한 성질
- 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree값만 1 감소시켜도 과정을 수행 가능
- indegree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가
구현 방법
- 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다
- indegree가 0인 정점들을 모두 큐에 넣는다
- 큐에서 정점을 꺼내어 위상 정렬 결과에 추가한다
- 해당 정점으로부터 연결된 모든 정점의 indegree값을 1 감소시킨다. 이 때, indegree가 0이 되었다면 그 정점을 큐에 추가한다
- 큐가 빌 때 까지 3, 4번을 반복한다
더보기
vector<int> adj[10];
int deg[10];
int n;
queue <int> q;
vector<int> result;
for (int i = 1; i <= n; ++i)
{
if (deg[i] == 0) q.push(i);
}
while (!q.empty())
{
int cur = q.front(); q.pop();
result.push_back(cur);
for (int nxt : adj[cur])
{
deg[nxt]--;
if (deg[nxt] == 0) q.push(nxt);
}
}
if (result.size() != n)
cout << "cycle exists";
else
{
for (auto& x : result) cout << x << ' ';
}
연습 문제
2252: 줄 세우기
더보기
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[32001];
queue<int> q;
vector<int> ans;
int ind[32001];
int n, m;
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
ind[b]++;
}
for (int i = 1; i <= n; ++i)
{
if (!ind[i]) q.push(i);
}
while (!q.empty())
{
int cur = q.front();
q.pop();
ans.push_back(cur);
for (auto& nxt : adj[cur])
{
ind[nxt]--;
if (!ind[nxt]) q.push(nxt);
}
}
for (auto& i : ans) cout << i << ' ';
return 0;
}
따로 ans에 결과를 저장하여 출력할 필요 없이 q의 루프 내에서 바로 출력해주면 된다
기본 문제
2623: 음악프로그램
더보기
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1001];
vector<int> ans;
queue<int> q;
int ind[1001];
int n, m;
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int k;
queue<int> tq;
cin >> k;
while (k--)
{
int a;
cin >> a;
tq.push(a);
}
int t = tq.front(); tq.pop();
while (!tq.empty())
{
int nxt = tq.front(); tq.pop();
adj[t].push_back(nxt);
ind[nxt]++;
t = nxt;
}
}
for (int i = 1; i <= n; ++i)
{
if (!ind[i]) q.push(i);
}
while (!q.empty())
{
int cur = q.front();
q.pop();
ans.push_back(cur);
for (auto& nxt : adj[cur])
{
ind[nxt]--;
if (!ind[nxt]) q.push(nxt);
}
}
if (ans.size() != n)
cout << 0;
else
{
for (auto& i : ans) cout << i << '\n';
}
return 0;
}
21276: 계보 복원가 호석
더보기
#include <bits/stdc++.h>
using namespace std;
int n, m;
map<string, int> h;
vector<int> adj[1001];
vector<string> sv;
vector<string> ans[1001];
int ind[1001];
int main(void)
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
sv.push_back("");
for (int i = 1; i <= n; ++i)
{
string s;
cin >> s;
sv.push_back(s);
}
sort(sv.begin()+1, sv.end());
for(int i = 1; i <= n; ++i) h.insert({sv[i], i});
cin >> m;
while (m--)
{
string s1, s2;
cin >> s1 >> s2;
adj[h[s2]].push_back(h[s1]);
ind[h[s1]]++;
}
vector<string> t;
queue<int> q;
for (int i = 1; i <= n; ++i)
{
if (!ind[i])
{
q.push(i);
t.push_back(sv[i]);
}
}
sort(t.begin(), t.end());
cout << t.size() << '\n';
for (auto& i : t) cout << i << ' ';
cout << '\n';
while (!q.empty())
{
int cur = q.front(); q.pop();
for (auto& nxt : adj[cur])
{
ind[nxt]--;
if (!ind[nxt])
{
q.push(nxt);
ans[cur].push_back(sv[nxt]);
}
}
}
for (int i = 1; i <= n; ++i)
{
cout << sv[i] << ' ' << ans[i].size() << ' ';
if (ans[i].size() > 0)
{
t.clear();
for (auto& k : ans[i]) t.push_back(k);
sort(t.begin(), t.end());
for (auto& k : t) cout << k << ' ';
}
cout << '\n';
}
return 0;
}
그래프를 그려보면 진출차수가 0인게 루트가 되지만 그래프 방향을 반대로 바꾸어서 진입차수를 비교하는걸로 바꿈
사전순 출력이 필요해서 컨테이너들이 추가로 여러개 쓰임
단순히 자식의 숫자만 출력하면 최초 진입차수가 2 이상인 자식들까지 포함되기 때문에 진입차수가 1인 자식들만 따로 ans에 추가해서 출력해준다
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x1C] 플로이드-워셜 알고리즘 (0) | 2022.08.10 |
|---|---|
| [0x1B] 최소 신장 트리 (0) | 2022.08.08 |
| [0x19] 트리 (0) | 2022.08.08 |
| [0x18] 그래프 (0) | 2022.08.07 |
| [0x17] 우선순위 큐 (0) | 2022.08.07 |
