https://www.acmicpc.net/problem/2252
문제
> N명의 학생들을 키 순서대로 줄을 세우려고 한다.
> 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다.
> 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
> 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.접근
이 문제는 방향이 있는 그래프 문제를 푼다고 생각하고 접근한다. 그리고 "위상 정렬" 문제 라고한다.
입력으로 주어지는 학생의 키 우선도에 따라 방향 그래프에 관계를 저장하듯 저장해주고 동시에 해당 학생의 앞에 몇명이 와야하는지를 나타내기 위해 벡터를 하나 만들고 입력받은 학생 중 뒤 학생을 인덱스로 하여 1씩 누적해준다.
BFS를 통해 해당 벡터의 값이 0인 애들 부터 순서대로 가져오며 연결 된 애들을 추가로 불러오며 나열한다.
위상 정렬 이란?
방향 그래프에서 각 정점 간의 선후 관계를 만족하도록 정점들을 순서대로 나열하는 정렬 방법을 말한다.
이때, 그래프는 사이클이 없는 방향 그래프(DAG)여야 하며,
간선 A → B가 존재한다면 정렬 결과에서 A는 반드시 B보다 앞에 위치하게 된다.
문제해결
> 학생의 선 후 관계를 저장할 student벡터와 학생의 앞에 몇명이 있는지를 저장할 height 벡터를 선언해준다.
> 입력받은 관계의 수 만큼 관계를 입력받으며 student벡터에 관계를 방향을 고려하여 저장한다.
> height에 B에 들어온 학생을 인덱스로 값을 누적시켜준다.
> 큐를 하나 만들고 모든 학생을 순회하며 height의 값이 0인 학생을 큐에 넣어준다.
> 큐가 빌 때 까지 BFS를 해주는데 큐의 맨 앞에서 잡혀온 애들은 앞에 누가 없거나, 상관없거나, 이미 선행 관계에 대한 처리가 끝난 애들이므로 출력해준다.
> 이제 큐에 다음 애들을 넣어주는데 맨앞에서 잡아온 학생과 관계된 학생을 모두 가져온다.
> 이 때, 방금 학생 한명 처리했으므로 관계된 학생들의 height값을 전부 1씩 감소시켜준다.
> 감소되어 새로 갱신 된 height값이 0이라면 또 앞에 아무도 없다는 뜻으로 보고 이 학생을 큐에 넣어 반복한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M, A, B;
vector<vector<int>> student;
vector<int> height;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
student.resize(N + 1); //관계도
height.assign(N + 1, 0); //차수
while (M--)
{
cin >> A >> B;
student[A].push_back(B);
height[B]++;
}
queue<int> q;
for (int i = 1; i <= N; i++)
{
if (height[i] != 0) continue;
q.push(i);
}
while (!q.empty())
{
int fh = q.front();
q.pop();
cout << fh << " ";
for (auto a : student[fh])
{
height[a]--;
if (height[a] != 0) continue;
q.push(a);
}
}
}
후기
감이 안잡혀서 알고리즘 분류를 봤더니 비순환 방향그래프, 위상정렬로 분류되고 있었다. 위상정렬은 처음 보는거라 찾아보았다. 선 후 관계가 주어지고 이를 유의 하며 그래프 탐색을 한다고한다. 그리고 순환이 생기면 선 후 관계가 무의미 해져버리기 때문에 성립하지 않는다. 사방,팔방 탐색하는 그래프 탐색 이외 처음 보는 유형이라 흥미로웠다.
