[백준] 1613번 : 역사

1613번: 역사

1613번: 역사

🤔 문제분석

위상정렬과 플로이드 워셜로 풀 수 있는 문제입니다. 저는 처음에 문제를 풀때 위상정렬로 접근하였습니다. 위상정렬을 할때에 **부모노드를 자식노드에 업데이트(부모노드는 자식노드에게 내가 너보다 먼저 야 라고 표시)**하면서 자기자신을 방문할때 자기자신을 추가하면 됩니다.

💻 코드

import sys
input = sys.stdin.readline
INF = sys.maxsize

n, k = map(int, input().split())

distance = [set() for _ in range(n+1)]
in_degree = [0 for _ in range(n+1)]
edge = [[] for _ in range(n+1)]
for _ in range(k):
    s, e = map(int, input().split())
    in_degree[e] += 1
    edge[s].append(e)

def dfs(node):
    for child in edge[node]:
        in_degree[child] -= 1
        distance[child] |= distance[node]
        if in_degree[child] == 0:
            distance[child].add(child)
            dfs(child)
            
root = []
for i in range(1, n+1):
    if in_degree[i] == 0:
        distance[i].add(i)
        root.append(i)

for i in root:
    dfs(i)
    
s = int(input())
for _ in range(s):
    s, e = map(int, input().split())
    if s in distance[e]:
        print(-1)
    elif e in distance[s]:
        print(1)
    else:
        print(0)
        

🎯 피드백 및 개선사항

플로드워셜로 문제를 해결 할 수 있으나 위상졍렬은 O(n+k) 시간복잡도이고 반면 플로이드워셜은 O(n^3)이라 훨씬 시간복잡도 측면에서 우위 인것을 알 수 있습니다. 플로이드워셜도 마찬가지로 d[s][e] = 1 로 표기 한뒤, d[s][k] and d[k][e] 가 존재한다면 s가 e보다 먼저 일어났다는걸 이용하여 문제를 풀면 됩니다.