2019.03.20) 소프트웨어 마에스트로 마지막 스퍼트 2편(위상정렬) - 1516, 2252, 3665 (PyPy3)

2019. 3. 20. 17:34프로그래밍(주력)/백준 문제풀이

위상정렬이 어려워보여 개념을 정리해보았다.

가중치가 있는 경우는 힙으로 우선순위큐를 하고,

간선만 주어지는 경우는 간단하게 큐로 구현하고(dfs)

이미 순서가 있다면 그래프를 그리는 법을 알수 있었다.


1516번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from heapq import heappush, heappop
 
= int(input())
 
graph = {i: list() for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
time = dict()
 
for i in range(1, N + 1):
    inp = list(map(int, input().split()))
    time[i] = inp[0]
 
    for j in range(1len(inp) - 1):
        graph[inp[j]].append(i)
        count[i] += 1
 
 
queue = list()
result = dict()
for i in range(1, N + 1):
    if count[i] == 0:
        heappush(queue, (time[i], i))
 
for _ in range(N):
    w, now = heappop(queue)
    result[now] = w
 
    for nxt in graph[now]:
        count[nxt] -= 1
        if count[nxt] == 0:
            heappush(queue,(w + time[nxt], nxt))
 
for i in range(1, N + 1):
    print(result[i])
cs

2252번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
N, M = map(int, input().split())
 
graph = {i: list() for i in range(1, N + 1)}
count = {i: 0 for i in range(1, N + 1)}
 
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    count[b] += 1
 
queue = list()
for i in range(1, N + 1):
    if count[i] == 0:
        queue.append(i)
 
result = ''
for _ in range(N):
    now = queue.pop(0)
    result += str(now) + ' '
    for nxt in graph[now]:
        count[nxt] -= 1
        if count[nxt] == 0:
            queue.append(nxt)
 
print(result)
 
 
 
cs

3665번

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
for _ in range(int(input())):
    N = int(input())
    st = list(map(int, input().split(' ')))
    N1 = int(input())
    graph = {i: {j: False for j in range(1, N + 1)} for i in range(1, N + 1)}
    count = {i: 0 for i in range(1, N + 1)}
    for i in range(N):
        for j in st[i + 1:]:
            graph[st[i]][j] = True
            count[j] += 1
 
    for i in range(N1):
        a, b = map(int, input().split(' '))
        if graph[a][b]:
            graph[a][b] = False
            graph[b][a] = True
            count[a] += 1
            count[b] -= 1
        else:
            graph[a][b] = True
            graph[b][a] = False
            count[b] += 1
            count[a] -= 1
 
    is_start = False
    is_double = False
    for i in range(1, N + 1):
        if not is_start and count[i] == 0:
            is_start = True
            start = i
        elif is_start and count[i] == 0:
            is_double = True
            break
    if is_double:
        print('?')
    elif is_start:
        result = list()
        queue = list()
        queue.append(start)
 
        for i in range(1, N + 1):
            if not queue:
                print('IMPOSSIBLE')
                break
            now = queue.pop(0)
            result.append(now)
            for nxt in range(1, N + 1):
                if graph[now][nxt]:
                    count[nxt] -= 1
                    if count[nxt] == 0:
                        queue.append(nxt)
        else:
            for i in result:
                print(i, end=' ')
            print()
 
    else:
        print('IMPOSSIBLE')
 
cs