백준 16958 텔레포트 / python

문제 : 16958

풀이 point

출발지, 도착지 도시 모두 특별한 도시라면, 텔레포트를 이용해서 이동할 수 있다.
그 외에는 |r1 - r2| + |c1 - c2|를 통해 직접 거리를 구해야한다.

먼저 직접 거리를 구한다. "출발지, 도착지 도시 모두 특별한 도시라면, 텔레포트를 이용해서 이동할 수 있다."라는 규칙을 통해 직접 거리보다 텔레포트를 이용하는 시간이 더 짧다면 그것을 택한다.

그 다음 플로이드 워셜을 통해 모든 정점으로부터 모든 정점으로까지의 최소거리를 구한다.

풀이 방법

플로이드 워셜은 유명하므로 따로 다루지는 않겠다. 3중 for문을 통해 모든 정점간의 최단 거리를 구하는 알고리즘이다.

플로이드 워셜은 O(N^3) 시간 복잡도를 가지므로 간신히 시간에 맞는다만... 아쉽게도 python에서는 특별한 방법이 아닌 이상 시간초과를 피할수 없다. C++의 경우에는 무난하게 통과하는 것 같다.

왜인지는 모르겠지만, 다음 코드와 같이 이중 for문을 통해 직접 거리를 구하는 방식이 시간 초과를 유발한다.

for i in range(N):
        for j in range(N):
            if i == j: continue
            d = abs(city[i][1] - city[j][1]) + abs(city[i][2] - city[j][2])
            if city[i][0] == 1 and city[j][0] == 1 and d > T:
                d = T
            dist[i][j] = d

다른 분의 코드를 참고해보니 이 이중 for문 부분을 다음과 같이 바꾸어야한다.

for i, j in combinations(range(N), 2):

이 부분만 바꾸면 시간 초과가 일어나지 않는다...

근데 이렇게 푸는게 아니다?

물론, 알고리즘 분류를 보면 플로이드-워셜 카테고리에 있기 때문에 플로이드 워셜로 풀어야한다고 생각할 수 있다. 하지만 다른 분들의 포스트를 참고해보니 4가지의 경우의 수를 통해 구할 수 도 있다.