플로이드-워셜 풀이가 궁금하다 : i와 j노드가 k로 연결되어있으면 i와 j도 연결되어있다.

코테연습을 하면서 '플로이드-워셜' 알고리즘을 활용한 문제를 마주했다.

처음에는 '플로이드-워셜' 알고리즘이 무엇인지 몰랐던 상태라 해당 알고리즘을 먼저 공부했고, 이를 문제에 활용했는데

개념은 알겠으나 왜 이렇게 적용하는지 이해가 되지 않은 부분이 있었다.

문제는 백준의 11403번 문제로 확인했다.

11403번: 경로 찾기

---

"""
3
0 1 0
0 0 1
1 0 0
"""
n = 3
city = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]

1. 처음 풀이 : 오답

처음엔 "세개 노드를 확인하면서 첫번째와 세번째의 노드가 모두 두번째 노드와 연결되어있으면 첫번째와 세번째 노드도 연결 된것" 이라는 개념으로 아래와 같이 풀었었다.

def solution_my():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
    
""" 연결 체크 이후 답
0 1 1
1 1 1
1 1 1
"""

하지만 0에서 0으로 가는 경로가 체크되지 않았다. 0 -> 1 / 1 -> 2 / 2 -> 0 경로가 존재하기 때문에 0 -> 0 의 경로도 체크되야 한다.

위와같은 오류가 발생한 까닭은

0에서 연속적으로 연결된 노드 정보를 미쳐 파악하기 전에 노드 0의 연결정보 파악이 끝났기 때문이다.

i = 0 / j = 2 / k = 1 일때 i와 j의 연결정보를 갱신한다 citi[0] = [0 1 0] -> [0 1 1]

이후 i는 1로 갱신되어 0번째 노드의 탐색이 종료된다.

 

위 과정을 2번 반복하면 이전에 체크되지 않은 노드가 체크되어 정답이 된다.

for _ in range(2):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
"""
1 1 1
1 1 1
1 1 1
"""

 

하지만 2번확인해도 누락이 생긴다면? 이 방법으로는 오류를 근본적으로 해결할 수 없다.

다시 플로이드-워셜의 풀이로 왜 성공했는지 확인해보자.

2. 플로이드-워셜 풀이

def solution_floid():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
""" 탐색 후 city 값
1 1 1
1 1 1
1 1 1
"""

내 풀이와 달리 모든 노드탐색이 확인되어 한번에 정답이 나왔다. (0에서 0으로 가는 경로도 체크되었다)

내 풀이와 위 풀이가 다른점은 탐색 노드 (k) 를 첫번째 for loop값으로 했다는 것이다.

즉, 시작노드가 i이고 종료노드가 j 일때 그 사이에 k 노드가 있는지 확인했던 내 풀이와 달리

탐색 노드 k를 기준으로 시작노드가 i일때 종료노드가 j이게 되는 수를 파악한 것이다.

 

플로이드-워셜 풀이를 기준으로 하면 가장 먼저 확인되는 추가 경로는 [2,1] 이다 해당 경로는 k 값이 0일때 2->0 이고, 0->1인게 확인되어 추가된다.

그 다음으로 추가되는 경로는 [0,2]이며 k값 1을 통해 경로가 확인된다. 위 방법의 풀이는 시작노드 값을 반복해서 확인하므로 내 풀이에서 0번 노드의 탐색을 바로 종료한것과 달리 k값을 탐색할때마다 확인하게 된다.

i값이 0이고, j값도 0일때 k 값에 따른 탐색 결과를 확인해 보면 다음과 같다.

#1 i=0, j=0, k=0 -> No
#2 i=0, j=0, k=1 -> No
"""
이때 i가 0이고, j가 2인 상황에서 k가 1일때 연결정보가 확인되므로
city[0][2] 값이 1로 갱신된다.
"""
#3 i=0, j=0, k=2 -> Yes
"""
위 과정으로 city[0][2]가 기존에 연결되지 않은 정보에서 갱신되었고,
city[2][0]은 원래 연결정보가 존재했으므로
city[0][0]에 대한 연결정보가 갱신된다.
"""

---

직접 풀이를 써내려가며 확인해 보니 왜 탐색노드를 첫번째 for loop 로 두었는지 감은 오지만, 아직까지 남에게 설명할 정도로의 감은 익히지 못한듯 하다. 추가로 플로이드-워셜 문제를 계속해서 풀면서 감을 익혀야 겠다.

!! 가중치가 주어진 상황 문제 풀어보기 !!