[백준] 1613번 - 역사 (파이썬)

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

# 역사
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

arr = [[False]*(N+1) for _ in range(N+1)]
for a in range(1, N+1):
    for b in range(1, N + 1):
        if a == b:
            arr[a][b] = False

for _ in range(M):
    a, b = map(int, input().split())
    arr[a][b] = True

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if arr[i][k] and arr[k][j]:
                arr[i][j] = True

K = int(input())
for _ in range(K):
    i, j = map(int, input().split())
    if arr[i][j] and not arr[j][i]:
        print(-1)
    elif not arr[i][j] and arr[j][i]:
        print(1)
    elif not arr[i][j] and not arr[j][i]:
        print(0)

 

플로이드와샬

1. 인접행렬을 선언하고 자기자신으로 가는 경우는 False로 초기화

2. 입력을 받으면서 True로 초기화

3. 플로이드 와샬

    - k를 거쳐서 가는 경로가 있으면 True

4. 탐색할 경우의 수 K번 만큼 i, j를 입력을 받고

    - i에서 j로 가는 경로는 있고 j에서 i로 가는 경로가 없으면 print(-1)

    - i에서 j로 가는 경로는 없고 j에서 i로 가는 경로가 있으면 print(1)

    - i에서 j로 가는 경로도 없고 j에서 i로 가는 경로도 없으면 print(0)

 

 

a가 b보다 먼저 일어난 사건이면 arr[a][b] = True

동시에 일어난 경우는 없으므로 경로가 있으면 먼저 일어난 사건이다.

둘다 경로가 없으면 알 수 없다.

 

같은 아이디어로 푸는 문제 : https://2hs-rti.tistory.com/104

[백준] 10159번 - 저울 (파이썬)