플로이드 워셜 주의해야할 점(k > i > j 순서로 돌기)

2224번: 명제 증명

 

명제가 주어질때 참으로 가능한 명제들을 모두 출력하는 문제

 

p => p같은 전건과 후건이 같은 명제는 출력하지 말고

 

삼단논법에 의해서만 참이 될 수 있는 명제만 출력하는 문제

 

전건 후건으로 가능한 것은 알파벳 대소문자이고 총 52개여서 이를 노드 번호로 바꿔주고

 

from sys import stdin

n = int(stdin.readline())

node = {chr(i+65):i for i in range(26)}

for i in range(26,52):
    
    node[chr(i+71)] = i

change = {v:k for k,v in node.items()}

 

 

A => b,  b => C이면 A노드에서 b노드로 갈 수 있다는 의미이고, b노드에서 C노드로 갈 수 있다는 의미이다

 

그래프로 만들고 52개 노드니까 O(N^3)으로 플로이드 워셜을 이용해 노드간 최단 거리를 찾는다

 

최단 거리가 1 이상이면 각 노드끼리는 이동가능하다는 의미이다

 

for _ in range(n):
    
    s = stdin.readline().rstrip().split()

    p = s[0]
    q = s[2]
    
    dp[node[p]][node[q]] = 1

for k in range(52):
    
    for i in range(52):
        
        for j in range(52):
            
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j])

answer = []

for i in range(52):
    
    for j in range(52):
        
        if i != j and dp[i][j] != INF and dp[i][j] >= 1:
            
            answer.append((change[i],change[j]))

answer.sort()

print(len(answer))

for i in range(len(answer)):
    
    a,b = answer[i]
        
    print(f'{a} => {b}')

 

 

여기서 핵심은 dp[i][j] != INF여야함

 

INF이면 이동 불가능하다는 뜻이기 때문

 

그리고 i = j인 부분은 제외해야함

 

왜냐하면 p => p같이 전건 후건이 같은 명제는 출력하지 마라했기 때문

 

그리고 처음에 초기화할때 dp[node[p]][node[q]] = 1로 했는데 p = q인 경우가 있을 수 있고 이 경우에 거리를 1로 했기 때문에

 

i != j 안하면 같은 경우가 나온다는 거임

 

---------------------------------------------------------------------------------------------------------------------------------------------------------

 

별거 없는 문제긴한데 이걸 적는 이유는.. 플로이드 워셜에서 k > i > j 순서로 순회하는거 아니면 틀린다는거다

 

for k in range(52):
    
    for i in range(52):
        
        for j in range(52):
            
            dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j])

 

 

알고리즘의 본질적인 의미로 생각해보면

 

플로이드 워셜 알고리즘은 그래프에서 i번에서 j번으로 집합 {1,2,3,...,k}의 노드만을 경유로 거쳐 최단 경로를 구하는데

 

최종 목표는 {1,2,..,N}의 노드만을 거쳐 i번에서 j번으로 가는 모든 순서쌍 (i,j)의 최단 경로를 찾는 알고리즘이다

 

그러니까 k = 1에서 i번에서 j번으로 {1}을 거쳐가는 최단 경로

 

k = 2에서 i번에서 j번으로 {1,2}를 거쳐가는 최단 경로

 

k = 3에서 i번에서 j번으로 {1,2,3}을 거쳐가는 최단 경로

 

....

 

k = N에서 i번에서 j번으로 {1,2,3,..,N}의 노드만을 거쳐가는 최단 경로

 

를 점진적으로 구해나간다

 

그런데 i번에서 j번으로 {1,2,..,k}의 노드만을 거쳐가는 최단 경로는 둘중 하나이다.

 

1) k를 통과하지 않거나

 

2) k를 통과하거나 

 

k를 통과하지 않는 경우는 i번에서 j번으로 {1,2,..,k-1} 노드만을 경유하여 거쳐가는 최단 경로

 

k를 통과하는 경우는 i번에서 k번까지 {1,2,..,k-1}노드를 경유하여 거쳐가는 최단 경로 + k번에서 j번까지 {1,2,..,k-1} 노드를 경유하여 거쳐가는 최단 경로

 

그래서 dp[i][j][k] = i번에서 j번까지 {1,2,..,k} 노드를 경유하여 거쳐가는 최단 경로

 

dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1])

 

dp[i][j][k]를 구할 때 

 

dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1] 중 최솟값을 새로운 위치를 만들어 dp[i][j][k]에 두는건데

 

굳이 한단계 깊이를 늘려 새로운 위치에 저장할 필요없이

 

dp[i][j], dp[i][k] + dp[k][j]중 최솟값을 dp[i][j]에 새롭게 저장해두고 다음 단계에서 

 

다시 dp[i][j], dp[i][k] + dp[k][j]중 최솟값을 dp[i][j]에 새롭게 저장해두고...

 

그니까 원래 (i,j)위치에 저장해두고 다음 단계로 넘어가면 되는데 이전 단계값을 남겨두고 새로운 위치를 만들어서 사용한다는 느낌이라고 해야할까

 

메모리 낭비잖아

 

어쨌든 알고리즘의 근본 원리를 읽어보면

 

모든 (i,j)쌍에 대해 1부터 k이하의 노드만을 경유하며 가는 최단 경로를 구하는 알고리즘으로 최종 목표는

 

k = n일때 (1,2,..,n)의 노드만을 경유하며 모든 (i,j)쌍에 대해 가는 최단 경로를 구하는 것

 

따라서 k = 1 부터 하나씩 증가해가야하기 때문에 반드시 중간지는 첫번째에 돌아야한다는거