[파이썬] 백준 1613 : 역사 (골드3)

[파이썬] 백준 1613 : 역사 (골드3)

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

---

풀이

방향성 생각

• 특정 거리를 묻는다기 보다는 순서를 묻는 문제.
• 위상 정렬이나 유니온파인드 + BFS로 생각한 풀이들은 중복 계산이 많이 발생해서 패스
• 플로이드와샬로 테이블을 업데이트 한 후, 간선 정보를 이용해서 출력한다.

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()
N,K = map(int,input().split())

# 간선 정보 업데이트
V = [[0]*(N+1) for _ in range(N+1)]
for _ in range(K):
    a,b = map(int,input().split())
    V[a][b] = 1

# 플로이드와샬. start -> transfer -> end : 둘 다 간선이 있는 경우에 start -> end
for t in range(1,N+1):
    for s in range(1,N+1):
        for e in range(1,N+1):
            if V[s][t] and V[t][e]:
                V[s][e] = 1

# 출력용 변환 table 만들기
table = {(1,0):-1, (0,1):1, (0,0):0}
for _ in range(int(input())):
    a,b = map(int,input().split())
    v,vr = V[a][b],V[b][a]
    print(table[(v,vr)])

코멘트

• 유니온파인드 + BFS로 풀이하려 했는데, 루트역할을 하는 노드가 여러개일 경우 찾기가 힘들다.
• 찾을 수 있는데, 시간이 굉장히 빡빡해보여서 플로이드와샬로 테이블 업데이트 후 출력만 해주는 것으로 변경.