프로그래머스 합승택시요금 문제 in python

프로그래머스 합승택시요금 문제

사용 알고리즘: 다익스트라 알고리즘
다익스트라 알고리즘을 사용하여 각 노드까지 합승할떄까지의 요금과, 택시에서 내려 각자의 집까지 갈 떄의 최저비용(최단거리)를 합해가며 비교해주는 문제이다.
문제 명세 참고:https://programmers.co.kr/learn/courses/30/lessons/72413
틀렸던 부분: 입력 요금이 100000까지 입력된다하여 max값을 100001로 두고 비교하도록 하였는데, 다시 생각해보니 여러 요금들이 더해질텐데(ex 100000+99000등등)
이럴 경우 max값보다 커서 100001이 리턴되게된다. max를 여유있게 주었어야했다.
입력받은 fares리스트를 가지고 graph 2차원배열을 만들어서 활용하였고, 각 지점까지 dijkstra알고리즘을 돌린 값(최저비용)과 해당 지점에서 각자의 집까지의 dijsktra값을 더해가며 최저비용을 구했다.
그런데 메인 그래프에서 연결되지않은 노드(길이 없는 곳)이 있을 수 있으므로 이를 예외처리 해주기 위하여 minnode에서 방문하지 않은 최단거리 노드가 존재하지 않을경우 ans값이 그대로 0으로 나오는점을 이용하여 예외처리 해주었다.(이 경우, 연결된 모든 길을 검색했음에도 목적지까지의 경로를 구해내지 못하였으므로 최단거리가 존재하지않는, 도달할 수 없는 경로로 취급하여 답을 구하는 과정에서 제외)

새로 배운 내용! 파이썬에서 배열을 동적 할당해줄때에는
아래와 같이 [[n(임의의 수) for i in range(column크기)]for k in range(row)]]이런 식으로 선언 해 주면 된다!

graph=[[]]
 #사전 graph 작업
def pre(n,fares):      
    global graph
    graph=[[100000001 for col in range(n+1)]for i in range(n+1)]
    for i in range(n+1):
        for k in range(n+1):
            if i==k:
                graph[i][k]=0
            elif i==0 or k==0:
                graph[i][k]=0
    for i in fares:
        graph[i[0]][i[1]]=i[2]
        graph[i[1]][i[0]]=i[2]
#가장 비용이 적은 노드 찾는 함수
def minnode(v,f):#방문하지 않은 노드들 중 최단거리의 노드를 구함
    ans=0
    min=100000001
    for i in range(1,len(v)):
        if f[i]<min and v[i]==False:
            min=f[i]
            ans=i
    if ans==0:#연결할수 있는 최단거리 노드가 존재하지 않는 경우
        return -1
    else:
        return ans


def dijk(start,fin,n):#다익스트라알고리즘
    if start==fin:
        return 0
    else:
        global graph
        flist=[0 for i in range(n+1)]
        visit=[False for i in range(n+1)]
        for i in range(1,(n+1)):
            if i==start:
                flist[i]=(100000001)
                visit[i]=(True)
            elif graph[start][i]!=100000001:
                flist[i]=(graph[start][i])
            else:
                flist[i]=100000001
        rc=True
        while visit[fin]!=True:
            curr=minnode(visit,flist)
            if curr==-1:
                rc=False
                break
            else:
                visit[curr]=True
                for i in range(1,n+1):
                    if flist[curr]+graph[curr][i]<flist[i] and visit[i]==False:
                        flist[i]=flist[curr]+graph[curr][i]
        if rc==False:
            return 100000001
        elif rc==True:
            return flist[fin]
def solution(n, s, a, b, fares):
    answer = 100000001
    if len(fares)==3:
        answer=fares[0][2]+fares[1][2]+fares[2][1]
    else:
        pre(n,fares)
        for i in range(1,n+1):
            answer=min(answer,dijk(s,i,n)+dijk(i,a,n)+dijk(i,b,n))
    return answer