Binary Journey

[Algorithm] 위상정렬 문제풀이 본문

Algorithm/알고리즘 스터디(2021.07)

[Algorithm] 위상정렬 문제풀이

binaryJournalist 2021. 11. 16. 00:10
반응형

 

 

 

 

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

 

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

 

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 32001

using namespace std;

int n, inDegree[MAX], result[MAX];
vector<int> a[MAX];

void topologySort() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) q.push(i);
	}
	
	for (int i = 1; i <= n; i++) {
		int x = q.front();
		q.pop();
		result[i] = x;
		for (int j = 0; j < a[x].size(); j++) {
			int y = a[x][j];
			if (--inDegree[y] == 0) q.push(y);
		}
	}
	
	for (int i = 1; i <= n; i++) {
		printf("%d", result[i]);
	}
}

int main(void) {
	int m;
	scanf("%d %d", &n, &m);
	for (int i= 0; i < m;i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		a[x].push_back(y);
		inDegree[y]++;
	}
	topologySort();
}

 

안돼!!!

 

from collections import deque

MAX = 32001
inDegree = [0 for i in range(MAX)]
result = [0 for i in range(MAX)]
a = [[] for i in range(MAX)]

def topologySort(number):
    q = deque()
    for i in range(1, number + 1):
        if inDegree[i] == 0:
            q.append(i)
    for i in range(1, number + 1):
        x = q.popleft()
        result[i] = x
        for j in range(0, len(a[x])):
            y = a[x][j]
            inDegree[y] -= 1
            if inDegree[y] == 0:
                q.append(y)
    for i in range(1, number+1):
        print(result[i])
        
if __name__ == "__main__":
    # n, m = map(int, input().split())
    n = 3
    m = 2

    # for i in range(m):
    #     x, y = map(int, input().split())
    #     a[x].append(y)
    #     inDegree[y] += 1
    # a[3].append(2)
    # inDegree[2] += 1
    a[1].append(3)
    inDegree[3] += 1
    a[2].append(3)
    inDegree[3] += 1
    topologySort(n)

참고: https://suri78.tistory.com/202

 

 

 

 

 

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

 

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부

www.acmicpc.net

 

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 501

using namespace std;

int n, inDegree[MAX], time[MAX], result[MAX];
vector<int> a[MAX];

void topologySort() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (inDegree[i] == 0) {
			result[i] = time[i];
			q.push(i);
		}
	}
	
	for (int i = 1; i <= n; i++) {
		int x = q.front();
		q.pop();
		for (int j = 0; j < a[x].size(); j++) {
			int y = a[x][j];
			result[y] = max(result[y], result[x] + time[y]);
			if (--inDegree[y] == 0) q.push(y);
		}
	}
	
	for (int i = 1; i <= n; i++) {
		printf("%d\n", result[i]);
	}
}

int main(void) {
	scanf("%d", &n);
	for (int i= 0; i < n;i++) {
		scanf("%d", &time[i]);
		while(1) {
			int x;
			scanf("%d", &x);
			if(x == -1) break;
			inDegree[i]++;
			a[x].push_back(i);
		}
	}
	topologySort();
}

 

 

 

안돼!!!!! 왜!!!

 

from collections import deque

MAX = 501
result = [0 for i in range(MAX)]
#time = [0 for i in range(MAX)]
#inDegree = [0 for i in range(MAX)]
#a = [[] for i in range(MAX)]

# inDegree = [ 0 for i in range(MAX)]
# time =  [0] * (MAX)
# result = []
# a = [[] for _ in range(MAX)]

a = [[], [2, 3, 4], [], [4, 5], [], []]
time=[0, 10 , 10, 4,4, 3]
inDegree= [0, 0, 1, 1, 2, 1]

def topologySort(number):
    q = deque()
    for i in range(1, number + 1):
        if inDegree[i] == 0:
            q.append(i)
            result[i] = time[i]
    while q:
        x = q.popleft()
        for y in a[x]:
            result[y] = max(result[y], result[x] + time[y])
            inDegree[y] -= 1
            if (inDegree[y] == 0): q.append(y)
    for i in range(1, number+1):
        print(result[i])
        
if __name__ == "__main__":
    n = 5

    # for i in range(1, n + 1):
    #     # temp = list(map(int, input().split()))
    #     time[i] = temp[0]
    #     for x in temp[1:]:
    #         if x == -1: break
    #         inDegree[i] += 1
    #         a[x].append(i)
    topologySort(n)

참고: https://donghak-dev.tistory.com/154

 

 

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

 

1948번: 임계경로

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의

www.acmicpc.net

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10001

using namespace std;

class Edge{
	public:
		int node;
		int time;
		Edge(int node, int time) {
			this -> node = node;
			this -> time = time;
		}
};

int n, start, finish;
int inDegree[MAX], result[MAX], c[MAX];
vector<Edge> a[MAX];
vector<Edge> b[MAX];

void topologySort() {
	queue<int> q;
	q.push(start);
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < a[x].size(); i++) {
			Edge y = Edge(a[x][i].node, a[x][i].time);
			if(result[y.node] <= y.time + result[x]) {
				result[y.node] = y.time + result[x];
			}
			
			if (--inDegree[y.node] == 0) {
				q.push(y.node);
			}
		}
	}
	int count = 0;
	q.push(finish);
	while(!q.empty()) {
		int y = q.front();
		q.pop();
		for (int i = 0; i < b[y].size(); i++) {
			Edge x = Edge(b[y][i].node, b[y][i].time);
			if (result[y] - result[x.node] == x.time) {
				count++;
				if (c[x.node] == 0) {
					q.push(x.node);
					c[x.node] = 1;
				}
			}
		}
	}
	printf("%d\n%d", result[finish], count);
}

int main(void) {
	int m;
	scanf("%d %d", &n, &n);
	for (int i= 0; i < m;i++) {
		int x, node, time;
		scanf("%d %d %d", &x, &node, &time);
		a[x].push_back(Edge(node, time));
		b[node].push_back(Edge(node, time));
		inDegree[node]++;
	}
	scanf("%d %d", &start, &finish);
	topologySort();
}

 

 

0 0 그만 나와,,

from collections import deque

MAX = 1001
result = [0 for i in range(MAX)]
check = [0 for i in range(MAX)]
time = [0 for i in range(MAX)]
inDegree = [0 for i in range(MAX)]
graph = [[] for i in range(MAX)]
back_graph = [[] for i in range(MAX)]
q = deque()

start = 1
end = 7

graph = [[], [(2, 4), (3, 2), (4, 3)], [(6, 3), (7, 5)], [(5, 1)], [(6, 4)], [(6, 2)], [(7, 5)], []]
back_graph= [[], [], [(1, 4)], [(1, 2)], [(1, 3)], [(3, 1)], [(2, 3), (4, 4), (5, 2)], [(2, 5), (6, 5)]]
inDegree = [0, 0, 1, 1, 1, 1, 3, 2]
# q.append(start)

def topologySort(number):
    while q:
        cur = q.popleft()
        for i, t in graph[cur]:
            inDegree[i] -= 1
            result[i] = max(result[i], result[cur] + t)
            if (inDegree[i] == 0): q.append(i)
    cnt = 0
    q.append(end)
    while q:
        cur = q.popleft()
        for i, t in back_graph[cur]:
            if result[cur] - result[i] == t:
                cnt += 1
                if check[i] == 0:
                    q.append(i)
                    check[i] = 1
    print(result[end])
    print(cnt)
        
if __name__ == "__main__":
    # n = int(input())
    # m = int(input())
    n = 7
    m = 9
    # for i in range(m):
    #     a, b, t = map(int, input().split())
    #     graph[a].append((b, t))
    #     back_graph[b].append((a, t))
    #     inDegree[b] += 1
    # start, end = map(int, input().split())
    q.append(start)

    topologySort(n)

참고: https://github.com/haidanliu19/Algorithms/blob/main/%EB%B0%B1%EC%A4%80/1948_%EC%9E%84%EA%B3%84%EA%B2%BD%EB%A1%9C.ipynb

참고: https://hiruby.tistory.com/439

반응형

'Algorithm > 알고리즘 스터디(2021.07)' 카테고리의 다른 글

[Algorithm] KMP 알고리즘  (0) 2021.11.22
[Algorithm] 단순 문자열 매칭 알고리즘  (0) 2021.11.22
[Algorithm] 이분 매칭 (Bipartite Matching)  (0) 2021.11.01
[Algorithm] 네트워크 플로우 (Network Flow)  (0) 2021.10.25
[Algorithm] 강한 요소 결합 (Strongly Connected Component, SCC)  (0) 2021.10.24
'Algorithm/알고리즘 스터디(2021.07)' Related Articles more