위상 정렬(Topological Sort), BFS 기반 + 2차원 배열

 위상 정렬이란 어떤 일들을 순서대로 해야 할  때, 선행 조건이 있는 작업들의 실행 순서를 정하는 방법이다. 방향 비순환 그래프(DAG, Directed Acyclic Graph)에서 적용가능하다. DFS기반과 BFS기반으로 구현할 수 있다. 이 글에서는 BFS기반으로 작성했다. 위상 정렬 알고리즘의 작동 과정은 아래와 같다.

 

1. 진입 차수가 0인 node를 queue에 넣는다.

2. queue에 넣은 노드의 다음 node의 진입차수를 1 줄인다.

3. q가 비어있을 때까지 2를 반복한다.

 

코드로 작성하면 아래와 같다.

 

int st[32001]; // 노드들의 진입차수
vector<int> graph[32001]; // 노드 연결
int N; // 노드의 수

queue<int> q;
vector<int> ans;

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

	while (!q.empty()) {
		int curr = q.front();
		q.pop();
		ans.push_back(curr);
		for (auto i : graph[curr]) {
			st[i]--;
			if (st[i] == 0) q.push(i);
		}
	}
}

관련 문제: https://www.acmicpc.net/problem/2252 G3

 

 

2차원 배열(격자 무늬)에서도 활용할 수 있다. 구현 방식은 같다.

int N;
int map[1001][1001];
bool visited[1001][1001];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

queue<pair<int, int>> q;
vector<pair<int, int>> v;

void ts() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) {
				q.push({ j, i });
				v.push_back({ j, i });
				visited[i][j] = true;
			}
		}
	}

	while (!q.empty()) {
		int cx = q.front().first;
		int cy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			map[ny][nx]--;
			if (map[ny][nx] == 0 && !visited[ny][nx]) {
				q.push({ nx, ny });
				v.push_back({ nx, ny });
				visited[ny][nx] = true;
			}
		}
	}
}

관련 문제: https://www.acmicpc.net/problem/31854 G3