백준 2252 c++ "줄 세우기" -PlusUltraCode-

https://www.acmicpc.net/problem/2252

 

 

 

 

[필자 사고]

특정 노드들간의 순서가 정해져 있다고 한다.

즉 위상정렬 알고리즘을 이용하여 문제를 풀 수 있다.

 

위상 정렬 알고리즘을 설명하면 다음과 같다.

D[N+1] 라는 배열이 있다.

 

1->3 이라고 입력값이 주어지면 

D[3]++ 하는식으로 하나를 증가 시켜준다. 

2 -> 3 이라고 입력값이 주어지면 D[3]++ 해준다.

 

위와같은 과정을 거친 후

 

BFS알고리즘을 통해 nowIdx -> nextIdx 일 경우

D[nextIdx]-- 하나를 빼주고 만약 D[0]==0 이 되면 myQueue에 nextIdx를 넣으면 된다.

 

초기 큐에 들어갈 idx 는 D[nowIdx] ==0 인 경우 모두 넣으면 된다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int N, M;

vector<vector<int>> arr;
vector<int> D;
vector<int>resultTank;

void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	D.resize(N + 1,0);
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		D[end]++;
		arr[start].push_back(end);
	}
}


void BFS() {
	queue<int> myQueue;
	vector<bool> visited;
	visited.resize(N + 1, false);

	for (int i = 1; i <= N; i++) {
		if (D[i] == 0) {
			myQueue.push(i);
			resultTank.push_back(i);
		}
	}

	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();
		visited[nowIdx] = true;

		for (int nextIdx : arr[nowIdx]) {
			if (visited[nextIdx] == true) continue;
			D[nextIdx]--;
			if (D[nextIdx] == 0) {
				myQueue.push(nextIdx);
				resultTank.push_back(nextIdx);
			}
		}
	}
}

void GameStart() {
	BFS();
	for (int i = 0; i < resultTank.size(); i++) {
		cout << resultTank[i] << " ";
	}
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	Input();
	GameStart();
}