백준 1753번: 최단경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

---

 

내가 생각했던 풀이는

graph[][] 2차원 배열을 만들어서, 노드1에서 노드2로 갈 때의 가중치를 저장한다. (graph[노드1][노드2]=가중치) 

거리를 저장할 dist 라는 1차원배열을 만들어 INF 값으로 초기화 해놓는다.

bfs함수를 만들고..

저장되어있던 dist[다음 노드]값과 dist[현재노드]+다음노드까지의 가중치 를 비교해서 더 작은값을 dist[다음노드]에 저장하는식으로..

계속 반복하게 만든다.

 

 

 

 

from collections import deque

MAX=11
v,e=map(int,input().split()) #정점개수v, 간선개수e
start=int(input()) #시작정점번호start
graph=[[MAX]*(v+1) for i in range(v+1)] #간선정보를 저장할 2차원 배열. graph[정점1][정점2]==정점1에서 정점2까지의 가중치
for i in range(e):
    v1,v2,w=map(int,input().split()) #v1에서 v2로 가는 가중치w의 간선
    if(graph[v1][v2]>w):
        graph[v1][v2]=w 

INF=99999
dist=[INF]*(v+1) #start에서 index까지의 거리를 저장할 1차원배열

def bfs():
    queue=deque()
    queue.append(start)
    dist[start]=0 #현재위치에서 현재위치까지의 거리=0
    while queue:
        x=queue.popleft()
        for i in range(1,len(graph[x])):
            if(graph[x][i]!=MAX):#입력된 간선이 있을 때
                if(dist[i]>dist[x]+graph[x][i]): #저장되어있던 dist값보다 지금 이동하는 숫자가 더 작을 때
                    dist[i]=dist[x]+graph[x][i]
                    queue.append(i) #i로 이동..

bfs()
for i in range(1,len(dist)):
    if(dist[i]==INF):
        print("INF")
        continue
    print(dist[i])

 

 결과는~

메모리초과, 시간초과.

다익스트라 배우고 다시 풀어야함.