문제
요약
사건의 전후 관계가 주어진다. 물음에 대해 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.
분류
- 플로이드-워셜
- BFS, DFS
- 비트마스킹
풀이
1. 내 풀이 (플로이드 워셜)
2차원 리스트에 질문에 대한 답을 저장할 수 있다.
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
arr = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(k):
a, b = map(int, input().split())
arr[a - 1][b - 1] = -1
arr[b - 1][a - 1] = 1
for inter in range(n):
for r in range(n):
for c in range(n):
if arr[r][c] != 0:
continue
elif arr[r][inter] == 1 and arr[inter][c] == 1:
arr[r][c] = 1
elif arr[r][inter] == -1 and arr[inter][c] == -1:
arr[r][c] = -1
t = int(input())
for _ in range(t):
a, b = map(int, input().split())
print(str(arr[a - 1][b - 1]))
2. BFS
자식을 set으로 관리해 in 연산을 용이하게 한다.
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
graph = [set() for _ in range(n)]
for _ in range(k):
a, b = map(int, input().split())
graph[a - 1].add(b - 1)
new = [set() for _ in range(n)]
for i in range(n):
queue = deque([i])
visit = set()
while queue:
cur = queue.popleft()
if cur in visit:
continue
visit.add(cur)
for node in graph[cur]:
if node not in visit:
queue.append(node)
new[i] = visit
s = int(input())
for _ in range(s):
a, b = map(int, input().split())
if b - 1 in new[a - 1]:
print(-1)
elif a - 1 in new[b - 1]:
print(1)
else:
print(0)