[백준1613&파이썬] 플로이드 와샬 알고리즘은 모든 노드로부터 특정노드까지의 연결여부를 알 수 있다.

# 문제

백준 1613 역사 파이썬 풀이

1613번: 역사

 

# 코드

import sys

n,k = map(int,sys.stdin.readline().split()) # n : 사건의개수, k : 전후 관계의 개수
distance = [ [float('inf')] * (n+1) for _ in range(n+1)]

for _ in range(k) :
  a,b = map(int,sys.stdin.readline().split())
  distance[a][b] = 1

for i in range(n+1) :
  distance[i][i] = 0 # 자기자신 0으로 초기화

# 플로이드 와샬을 통해서 모든정점까지의 방문 가능성을 확인해야함
for pivot in range(1,n+1) :
  for start in range(1,n+1) :
    for end in range(1,n+1) :
      cost = distance[start][pivot] + distance[pivot][end]
      if cost < distance[start][end] :
        distance[start][end] = cost

s = int(sys.stdin.readline().strip()) # 전후 관계를 알고 싶은 사건의 쌍
targets = list()
for _ in range(s) :
  a,b = map(int, sys.stdin.readline().split())
  targets.append((a,b))


# 출력
  # 앞에 있는 사건이 먼저 일어났으면 -1
  # 뒤에 있는 사건이 먼저 일어났으면 1
  # 유추할 수 없으면 0

# print(distance)
for a,b in targets :
  fisrt = distance[a][b]
  second = distance[b][a]

  if fisrt == float('inf') and second == float('inf') :
    print(0) # 유추 할 수 없는 경우
  elif fisrt < float('inf') :
    print(-1)
  else :
    print(1)

 

# 풀이

• 문제를 해결하기 위해서는, 각 사건과 사건의 선행여부를 단방향그래프로 확장하여 생각해봐야 한다.
• 조건에 모순인 관계가 없다고 했기 때문에 사이클이 생기는 경우는 없을 것이다.
• 답을 구해야하는 사건의 순서쌍 (a,b)에 대해서 a->b로 이동이 가능한가? or b->a 로 이동이 가능한가? 로 나누어 생각해본다.
• 두조건중 하나라도 만족하면 -1 or 1을 출력하면 되고, a->b로 이동이 불가능하다면 유추할 수 없기 때문에 0을 출력하면 된다.
• 플로이드-와샬 알고리즘을 사용하면 모든 정점에서부터 모든 정점까지의 최단거리를 알 수 있다. 만일 distance의 값이 INF라면 이동이 불가능한 상태이다.
• BFS로 풀어볼까 생각했지만, 어차피 사건의 순서쌍 개수만큼 구해야 하기 때문에 플로이드와샬을 통해 한번에 구해놓고 답만 출력하면 도리거 같아서 플로이드 와샬을 선택하여 사용했다.