[백준] 역사 : 플로이드 와샬

seilk·2022년 3월 23일
0

자료구조-알고리즘

목록 보기
10/11

문제

1613번: 역사

아이디어

전체 노드 개수 : 1N4001≤ N ≤400

전체 경로의 개수 : 1k500001≤ k ≤50000

쿼리의 수 1s500001≤ s ≤50000

Naive한 접근 : 사건 a, b를 받았을 때 DFS 혹은 BFS를 사용하여 그래프 탐색

  • 최악의 경우 O(ks)O(ks)

쿼리의 개수가 많기 때문에 전처리를 해주면 좋을것으로 판단.

어떤 쿼리가 들어올지 모르기 때문에 모든 노드 to 모든 노드 **에 대한 정보를 전처리 해줘야함.

N to N(from N개의 노드 to N개의 노드) 의 경로를 구하는 방식으로 플로이드 와샬 알고리즘이 있다.

심지어 N의 크기가 작아서 O(N3)O(N^3)에 문제를 해결 할 수 있다.

풀이

주어지는 경로의 정보를 바탕으로 인접 리스트를 구현한다.

모든 노드가 한번씩 경유지가 될 수 있도록 해서 A노드에서 B노드로 가는 경로가 존재하는지에 대한 여부를 파악한다.

플로이드 와샬을 처음 공부할 때는 N to N 의 최단경로를 구하는 알고리즘으로 공부하는데

어떤 노드에서 다른 노드로 도달할 수 있는지 없는지에 대한 가능성을 파악하는 데 쓰일 수 있다.

플로이드 와샬 : 어떤 노드에서 다른 노드로 가는 경우의 수를 모두 탐색하는 알고리즘

💡플로이드 와샬 알고리즘을 최단경로 알고리즘으로 기억하는것이 아니라 어떤 노드에서 다른 노드로 가는 경우의 수를 모두 탐색하는 알고리즘이라고 기억하자.

코드

import sys
In = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, In().split())

def floyd(n):
   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] == True and arr[k][j] == True:
               arr[i][j] = True

n, k = MIS()
arr = [[0] * (n+1) for i in range(n + 1)]
for i in range(1, n + 1):
   arr[i][i] = 1

dp = [[0] * (n + 1) for i in range(n + 1)]
for _ in range(k):
   front, back = MIS()
   arr[front][back] = 1

floyd(n)

g = int(In())
for _ in range(g):
   u, v = MIS()
   if arr[u][v] == True:
      print(-1)
   elif arr[v][u] == True:
      print(1)
   else:
      print(0)
profile
seilk

0개의 댓글