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

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

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

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

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

1516번

from heapq import heappush, heappop
 
N = 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(1, len(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])

2252번

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)
 
 
 

3665번

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')