문제링크
https://www.acmicpc.net/problem/2252
풀이방법
해당 문제는 기본적으로 위상 정렬 알고리즘을 이용하여 쉽게 해결하였다. 학생 A가 학생 B앞의 서야 한다는 것은 A노드가 B노드를 가르키고 있다고 생각하여 그림을 그려보면 쉽게 이해가 갈 것이다. 그렇게 그린 그래프를 바탕으로 위상 정렬 알고리즘을 구현하면 된다.
위상 정렬 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자
해답 코드는 다음과 같다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[32005];
int deg[32005];
int n,m,u,v;
queue<int> q;
vector<int> result;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
while (m--)
{
cin >> u >> v;
adj[u].push_back(v);
++deg[v];
}
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 (auto nxt : adj[cur])
{
deg[nxt]--;
if (deg[nxt] == 0) q.push(nxt);
}
}
for (auto c : result) cout << c << ' ';
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
백준 1766번: 문제집 (C++) (0) | 2024.02.02 |
---|---|
백준 2623번: 음악프로그램 (C++) (0) | 2024.02.02 |
백준 1240번: 노드사이의 거리 (C++) (0) | 2024.02.02 |
백준 15681번: 트리와 쿼리 (C++) (0) | 2024.02.02 |
백준 4803번: 트리 (C++) (0) | 2024.02.02 |