Algorithm 공부 #15 - 그래프(위상 정렬)

 

Algorithm 공부 #15 - 그래프(위상 정렬)

 

 

위상 정렬(Topology Sort)

 

  ● 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

  ● 항상 유일한 값으로 정렬되지 않음

  ● 진입 차수 : 자기 자신을 가리키는 에지의 개수

  ● 원리 파악하기

        노드는 5개이고 각 노드는 1,2,3,4,5

        1번 노드는 2번과 3번 노드를 / 2번 노드는 4번과 5번 노드를 / 3번 노드는 4번 노드를

        4번 노드는 5번 노드를 가리키는 그래프가 있다고 가정하기

     

                                                                                              진입차수 배열 D[N] 

1	2	3	4	5
0	1	1	2	2

         

         진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하기

         그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼주기

         이 과정을 모든 노드의 진입 차수가 0일 될 때까지 반복

 

 

백준 2252번 줄 세우기

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

2252번: 줄 세우기

    

 

※ 위상 정렬 이용하는 문제 ※

● 인접 리스트A, 진입 차수배열 indegree, 위상 정렬 배열 queue를 생성

● A에 start와 end값을 입력받으면서 indegree[end]를 ++ 해줘서 진입 차수배열 값들 업데이트

● 업데이트가 끝난 후 indegree[i]==0인 값들을 queue에 push

● 큐에 있는 값들을 출력해주고 반복문을 돌리면서 indegree[i]가 0인 값을 큐에 푸쉬

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<vector<int>>A; // 입력받을 인접 리스트
	vector<int>indegree; // 진입 차수 배열
	A.resize(N + 1); 
	indegree.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		A[start].push_back(end); // 인접 리스트 업데이트
		indegree[end]++;// 진입 차수 업데이트
	}

	queue<int>queue;
	
	for (int i = 1; i <= N; i++) { // 진입 차수가 0인 값들 큐에 푸쉬
		if (indegree[i] == 0)
			queue.push(i);
	}

	while (!queue.empty()) {
		int now = queue.front();
		queue.pop();
		cout << now << " ";
		for (int next : A[now]) {
			indegree[next]--;
			if (indegree[next] == 0)
				queue.push(next);
		}

	}

}

 

 

백준 1516번 게임 개발

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

1516번: 게임 개발

 

※ 위상 정렬 이용하는 문제 ※

● 인접 리스트A, 진입 차수배열 indegree, 위상 정렬 배열 queue, 정답 배열 result, 시간 저장 배열 buildTime 생성

● A에 start와 end값을 입력받으면서 indegree[end]를 ++ 해줘서 진입 차수배열 값들 업데이트

● 업데이트가 끝난 후 indegree[i]==0인 값들을 queue에 push

● 걸리는 시간도 buildTime배열에 업데이트

● 큐를 돌리면서 result[next]에 max(result[next], result[now]+buildTime[now]값 저장

● 반복문을 돌리면서 result[i]+buildTime[i]값을 출력

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

vector<int>buildTime; // time을 저장할 배열
vector<vector<int>>A; // 입력받을 인접 리스트
vector<int>indegree; // 진입 차수 배열
vector<int>result; // 결과 출력 배열

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	buildTime.resize(N + 1); // 시간 배열 크기 조정
	A.resize(N + 1); // 인접 리스트 크기 조정
	indegree.resize(N + 1); // 진입 차수 배열 크기 조정
	result.resize(N + 1); // 결과 배열 크기 조정

	for (int i = 0; i <= N; i++) // 진입 차수 배열 0으로 초기화
		indegree[i] = 0;

	for (int i = 1; i <= N; i++) {
		int money;
		cin >> money;
		buildTime[i] = money; // 시간 입력
		while (true) {
			int x;
			cin >> x;
			if (x == -1)
				break;
			A[x].push_back(i); // 인접 리스트 업데이트
			indegree[i]++; // 진입 차수 배열 업데이트
		}
	}

	for (int i = 1; i <= N; i++) // 진입 차수 배열 0으로 초기화
		result[i] = 0;

	queue<int>myQueue;
	for (int i = 1; i <= N; i++) { // 진입 차수 0인 값들 큐에 푸쉬
		if (indegree[i] == 0) {
			myQueue.push(i);
		}
	}

	while (!myQueue.empty()) {
		int now = myQueue.front();
		myQueue.pop();
		for (int next : A[now]) {
			indegree[next]--;
			result[next] = max(result[next], result[now] + buildTime[now]);
			if (indegree[next] == 0)
				myQueue.push(next);
		}
	}

	for (int i = 1; i <= N; i++)
		cout << result[i]+buildTime[i]<< '\n';
}

 

 

 

백준 1948번 임계경로

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

1948번: 임계경로

※ 위상 정렬 이용하는 문제 ※

● 진입 차수배열과 인접 리스트를 업데이트 한 후 출발 지점에서부터 위상 정렬 수행

● 위 과정을 수행하게 되면 임계경로 배열이 모두 업데이트 완료 => result[endcity]가 걸리는 시간

● 1분도 쉬지 않고 달리는 사람을 찾기 위해서 역방향 리스트 업데이트(1번 과정 수행시 같이 함)

● 또다른 큐를 생성하고 끝지점을 큐에 push해주기

● 반복문을 돌리면서 visit배열로 방문 체크 여부 확인해서 중복으로 방문하지 않게 하기

● 그다음 도시의 임계 경로 == 그 다음 도시까지 가는데 걸리는 시간 + 지금 도시의 임계 경로이면

   쉬지 않고 달려야 하므로 count을 해줌

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

vector<vector<pair<int, int>>>A; // 입력받을 인접 리스트
vector<vector<pair<int, int>>>rev; // 역방향 도시 인접 리스트
vector<int>indegree; // 진입 차수 배열
vector<int>result; // 임계 경로 배열

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	A.resize(N + 1); // 인접 리스트 크기 조절
	rev.resize(N + 1); // 역방향 리스트 크기 조절
	result.resize(N + 1); // 임계 경롤 배열 크기 조절
	indegree.resize(N + 1); // 진입 차수 배열 크기 조절

	for (int i = 0; i < M; i++) {
		int start, end, time;
		cin >> start >> end >> time;
		A[start].push_back({ end,time }); // 인접 리스트 업데이트
		rev[end].push_back({ start,time }); // 역방향 리스트 업데이트
		indegree[end]++; // 진입 차수 배열 업데이트
	}

	int startcity, endcity;
	cin >> startcity >> endcity; //출발 도시와 도착 도시
	queue<int>timequeue; // 위상 정렬 큐
	timequeue.push(startcity); // 시작 도시 넣어서 시간 구하기
	
	while (!timequeue.empty()) {
		int now = timequeue.front();
		timequeue.pop();
		for (pair<int, int>cur : A[now]) {
			indegree[cur.first]--; // 진입 차수 배열 업데이트
			result[cur.first] = max(result[cur.first], result[now] + cur.second);
			if (indegree[cur.first] == 0)
				timequeue.push(cur.first);
		}
	}
	
	queue<int>revqueue; // 역방향 큐 생성
	revqueue.push(endcity); // 끝지점부터 출발
	vector<bool>visit;
	visit.resize(N + 1);
	visit[endcity] = true; // 중복 여부체크를 위해서 visit배열 생성
	int citycount = 0;

	while (!revqueue.empty()) {
		int now = revqueue.front();
		revqueue.pop();
		for (pair<int, int>cur : rev[now]) {
			if (result[now] == result[cur.first] + cur.second) {
				citycount++; // 위 조건이 성립하면 1분도 쉬면 안 되는 것이므로
				if (!visit[cur.first]) { // 방문하지 않은 곳만 탐색하기 위함
					visit[cur.first] = true;
					revqueue.push(cur.first);
				}
			}
		}
	}
	cout << result[endcity] << '\n' << citycount;
}