백준 2252 줄 세우기 C++

Nov 29, 2023

위상정렬 을 이용하는 문제였다. 태그를 보고 풀었는데 위상정렬을 몰라 알고리즘만 보고 바로 풀어봤는데 입력을 어떻게 받을 지가 고민이었다.

정점 v1에서 연결되어있는 다른 정점으로의 간선의 개수를 진출차수라고 하며,
다른 정점에서 v1으로 연결되어있는 간선의 개수를 진입차수라고 한다.

위상정렬은 순서가 정해진 정점들의 순서를 구하는 알고리즘으로, 동작과정은 다음과 같다.

진입차수가 0인 정점을 모두 큐에 PUSH
큐에서 정점을 하나 POP하고 그 정점에서 진출하는 모든 간선을 제거한다.(연결 된 정점의 진입차수 1씩 감소)
제거 한 후, 진입차수가 0이 된 정점이 있다면, 큐에 PUSH
큐가 빌 때 까지 반복한다.

처음엔 입력과 진입차수가 0이 된 정점을 큐에 넣는 구현을 어떻게 해야할 지 모르겠어서 그냥 for문으로 하나씩 확인해서 시간초과가 났다.

입력은 a정점->b정점순이므로
정점의 저장은 a정점의 백터에 b를 넣어주고, 진입차수를 저장할 배열 arr[b]++로 입력받았다.

	cin >> a >> b;
	out[a].push_back(b);
	arr[b]++;

가장 처음 진입차수가 0인 정점들을 큐에 넣을 때는 for문으로 돌며 넣어주고

	for (int i = 1; i <= N; i++)
		if (arr[i] == 0) { q.push(i); }

큐가 빌때까지 반복해주었다. 간선을 제거하는 것은 그냥 진입차수만 감소시켜주는 것으로 구현했다.

	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		cout << v << ' ';
		for (int i = 0; i < out[v].size(); i++)
		{
			//간선을 제거해 진입차수 1이 감소했을 때 0이라면
			if (--arr[out[v][i]] == 0)
			{
				//큐에 PUSH!
				q.push(out[v][i]);
			}
		}
	}

전체코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> out[32001]; //정점에서 연결된 다른 정점들을 저장할 벡터
int arr[32001]; //진입차수 저장배열
queue<int> q;
int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int a, b;
	cin >> N >> M;
	while (M--)
	{
		cin >> a >> b;
		out[a].push_back(b);
		arr[b]++;
	}
	for (int i = 1; i <= N; i++)
		if (arr[i] == 0) { q.push(i); }
	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		cout << v << ' ';

		for (int i = 0; i < out[v].size(); i++)
		{
			//간선을 제거해 진입차수 1이 감소했을 때 0이라면
			if (--arr[out[v][i]] == 0)
			{
				//큐에 PUSH!
				q.push(out[v][i]);
			}
		}
	}
	return 0;
}

글을 작성하기 전까지만 해도 코드가 엉망인 부분이 많았는데 작성 중에 개선할 점이 보여 수정해 시간과 공간도 더 줄일 수 있었다.