python 시간을 줄이는 테크닉 - min,max를 남발하지 말자(플로이드 워셜에서 주의하기)

16958번: 텔레포트 (acmicpc.net)

16958번: 텔레포트

 

이 문제에서 다음과 같이 제출하면.. 시간 초과로 통과하지 못한다

 

from sys import stdin

INF = 1e9

def floyd(graph,city):

    for k in range(1,n+1):
    
        for a in range(1,n+1):
            
            if k == a:
                continue

            for b in range(1,n+1):
                
                if a == b:
                    continue

                graph[a][b] = min(graph[a][b],graph[a][k] + graph[k][b])
    
    return graph

n,t = map(int,stdin.readline().split())

graph = [[INF]*(n+1) for _ in range(n+1)]

city = [0]

for _ in range(n):
    
    s,x,y = map(int,stdin.readline().split())

    city.append((s,x,y))

for a in range(1,n+1):
    
    for b in range(1,n+1):
        
        if a != b:
            
            x = abs(city[a][1] - city[b][1]) + abs(city[a][2] - city[b][2])
            
            if x > t and city[a][0] == 1 and city[b][0] == 1:
                
                graph[a][b] = t
            
            else:
                
                graph[a][b] = x
                
graph = floyd(graph,city)

m = int(stdin.readline())

for _ in range(m):
    
    a,b = map(int,stdin.readline().split())

    print(graph[a][b])

 

 

반면, floyd()함수에서 graph[a][b] = min(graph[a][b],graph[a][k] + graph[k][b])을 if문을 활용한 비교로 고치면..

 

if graph[a][b] > graph[a][k] + graph[k][b]: graph[a][b] = graph[a][k] + graph[k][b]

 

통과하게 되는데..

 

from sys import stdin

INF = 1e9

def floyd(graph,city):

    for k in range(1,n+1):
    
        for a in range(1,n+1):
            
            if k == a:
                continue

            for b in range(1,n+1):
                
                if a == b:
                    continue

                if graph[a][b] > graph[a][k] + graph[k][b]:

                    graph[a][b] = graph[a][k] + graph[k][b]
    
    return graph

n,t = map(int,stdin.readline().split())

graph = [[INF]*(n+1) for _ in range(n+1)]

city = [0]

for _ in range(n):
    
    s,x,y = map(int,stdin.readline().split())

    city.append((s,x,y))

for a in range(1,n+1):
    
    for b in range(1,n+1):
        
        if a != b:
            
            x = abs(city[a][1] - city[b][1]) + abs(city[a][2] - city[b][2])
            
            if x > t and city[a][0] == 1 and city[b][0] == 1:
                
                graph[a][b] = t
            
            else:
                
                graph[a][b] = x
                
graph = floyd(graph,city)

m = int(stdin.readline())

for _ in range(m):
    
    a,b = map(int,stdin.readline().split())

    print(graph[a][b])

 

그게 그거 아니냐 생각하고 생각없이 min() max()함수 써왔는데 그게 그거가 아닌가보다

 

https://stackoverflow.com/questions/56281691/why-is-max-function-so-much-slower-when-comparing-2-elements-vs-direct-compari

Why is max() function so much slower when comparing 2 elements vs direct comparison with an if statement?

 

min(), max()함수가 단순히 >으로 비교하는것보다 하는 일이 더 많아서 시간 차이가 생기나보다

 

 

 

근데 원소 수가 많아질수록 시간 차이가 줄어든다는게 설명인데 정말 그런가

 

원소 100개인 리스트 사용해보니까 오히려 min()함수가 압도적으로 빠름

 

 

 

아무튼 조금의 디테일이 의외로 결정적일수 있다는걸 알려주는거라고 해야할까

 

플로이드 워셜 알고리즘 if문으로 바꿔서 수정해야하나.. 허허

 

11404번: 플로이드 (acmicpc.net)

11404번: 플로이드

 

플로이드 워셜을 구현하는 연습문제다.

 

graph를 구성해서 O(N)으로 먼저 (i,i)는 못가니까 0으로 채워넣고

 

a에서 b로 가는 가중치 c를 입력받으면서 graph[a][b]값을 최솟값으로 갱신시켜나가고..

 

여기서 최솟값으로 갱신시켜나간 이유는... 문제에서 "a에서 b로 가는 간선이 하나가 아닐 수 있다"라고 명시해서 그렇다

 

하나라는게 확실하면 graph[a][b] = c로 하면 되겠지

 

플로이드 워셜 알고리즘을 수행한다

 

from sys import stdin

n = int(stdin.readline())

m = int(stdin.readline())

INF = 1000000000000000000

graph = [[INF]*(n+1) for _ in range(n+1)]

for i in range(n+1):
    
    graph[i][i] = 0

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    if graph[a][b] > c:
        
        graph[a][b] = c

for k in range(1,n+1):
    
    for a in range(1,n+1):
        
        for b in range(1,n+1):
            
            graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])

for i in range(1,n+1):
    
    for j in range(1,n+1):
        
        if graph[i][j] == INF:
            
            print(0,end=' ')
        
        else:
            
            print(graph[i][j], end= ' ')
    
    print()

 

 

예전에 배운 알고리즘 그대로 적용한거인데 min()함수 써서 해가지고 여기도 min()함수 사용했는데

 

이게 0.7초더라

 

for k in range(1,n+1):
    
    for a in range(1,n+1):
        
        for b in range(1,n+1):
            
            graph[a][b] = min(graph[a][b],graph[a][k]+graph[k][b])

 

 

근데 저 min()을 if문 비교로 바꿔보니.. 0.3초더라고.. 절반이 줄어든다.

 

from sys import stdin

n = int(stdin.readline())

m = int(stdin.readline())

INF = 1000000000000000000

graph = [[INF]*(n+1) for _ in range(n+1)]

for i in range(n+1):
    
    graph[i][i] = 0

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    if graph[a][b] > c:
        
        graph[a][b] = c

for k in range(1,n+1):
    
    for a in range(1,n+1):
        
        for b in range(1,n+1):
            
            if graph[a][b] > graph[a][k] + graph[k][b]:
            
                graph[a][b] = graph[a][k]+graph[k][b]

for i in range(1,n+1):
    
    for j in range(1,n+1):
        
        if graph[i][j] == INF:
            
            print(0,end=' ')
        
        else:
            
            print(graph[i][j], end= ' ')
    
    print()

 

 

여담으로 플로이드 워셜 알고리즘 수행하는 부분을 floyd()함수 정의해서 사용해보면 0.2초정도..?

 

from sys import stdin

def floyd(graph):

    for k in range(1,n+1):
    
        for a in range(1,n+1):

            for b in range(1,n+1):

                if graph[a][b] > graph[a][k] + graph[k][b]:

                    graph[a][b] = graph[a][k]+graph[k][b]
    
    return graph

n = int(stdin.readline())

m = int(stdin.readline())

INF = 1000000000000000000

graph = [[INF]*(n+1) for _ in range(n+1)]

for i in range(n+1):
    
    graph[i][i] = 0

for _ in range(m):
    
    a,b,c = map(int,stdin.readline().split())

    if graph[a][b] > c:
        
        graph[a][b] = c

graph = floyd(graph)

for i in range(1,n+1):
    
    for j in range(1,n+1):
        
        if graph[i][j] == INF:
            
            print(0,end=' ')
        
        else:
            
            print(graph[i][j], end= ' ')
    
    print()

 

 

아무튼 원소 수가 적을때 min()함수를 if문 비교로 바꾸기만 해도 꽤 많은 시간 이득을 볼 수 있다