[Python] 프로그래머스 / 네트워크

문제링크
 

Floyd-Warshall

 
Dijkstra, Bellman-Ford와 함께 그래프에서 최적의 경로를 찾는 알고리즘으로는 Floyd-Warshall이 있다.
이중 Bellman-Ford는 사실 거의 쓸 일이 없고, 보통은 Dijkstra를 이용할 때가 많다. 일단 시간복잡도도 O(n^2)로 낮은 편이기 때문이다. 그러나 모든 i to j에 대한 정보가 필요하다면, Dijkstra를 n번 돌려 O(n^3)을 구현하는 것보다, Floyd-Warshall로 한큐에 O(n^3)로 끝내는 게 더 간결한 코드이다.

 
Floyd-Warshall 코드는 극도로 단순하다. k(경유지), i(출발지), j(종착지) 순으로 for문 돌리기만 하면 끝. 실전 코테에서 최적 경로 뿐만이 아니라 생각보다 다양한 용도로 Floyd-Warshall이 응용될 수 있으니, 이 코드를 적극 숙지하도록 하자.

for k in range(n): #경유지
    for i in range(n): #출발지
        for j in range(n): #종착지
            #원하는 코드를 여기에 구현
            #예를 들어,
            if length(i, k) + length(k, j) > length(i, j) :
                length(i, j) = length(i, k) + length(k, j)

            #혹은 다음과 같은 코드도 구현할 수 있음
            if not is_connected(i, j) :
                if is_connected(i, k) and is_connected(k, j):
                    is_connected(i, j) = True

 

정답 코드

 

from collections import defaultdict

def solution(n, computers):

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    world = defaultdict(list)

    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                if computers[i][j] == 0 and computers[i][k] == 1 and computers[k][j] == 1 :
                    computers[i][j] = 1

    seen = [0]*n
    i = 0
    answer = 0

    while not all(seen) :

        if i > n :
            break

        if not seen[i] : 
            answer += 1
            for j in range(n) :
                if computers[i][j] == 1 :
                    seen[j] = 1

        i += 1

    return answer