Programmers / 부대복귀(최단경로알고리즘 - 다익스트라) / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 부대복귀(최단경로알고리즘 - 다익스트라) - 3단계 

문제 사이트: https://school.programmers.co.kr/questions/51058

프로그래머스

---

나의 풀이 - 시간초과

bfs로 접근했는데 시간초과가 났다..

import sys

from collections import deque, defaultdict
input = sys.stdin.readline

def bfs(n,maps,start,end):
    queue = deque([[start,0]])
    visited = [0 for i in range(n+1)]
    min_cnt = 1e9
    while queue:
        q,cnt = queue.popleft()
        visited[q] = 1
        if q == end:
            min_cnt = min(min_cnt,cnt)
        if min_cnt > cnt and maps[q]:
            for i in maps[q]:
                if visited[i] == 0:
                        queue.append([i,cnt + 1])
        
    if min_cnt == 1e9:
        return -1
    else:
        return min_cnt
        
def solution(n, roads, sources, destination):
    answer = []
    
    # 경로에 따른 맵 만들기
    maps = defaultdict(set)
    for r in roads:
        maps[r[0]].add(r[1])
        maps[r[1]].add(r[0])
    
    for s in sources:
        a = bfs(n,maps,s,destination)
        answer.append(a)
    
    return answer

 

다른 풀이

- 이것도 시간 초과됨

import sys
from collections import deque, defaultdict
input = sys.stdin.readline

def dijkstra(n, maps, start, end):
    queue = deque([[start, 0]])
    dist = [1e9 for i in range(n+1)]
    dist[start] = 0
    min_cnt = 1e9
    while queue:
        q, cnt = queue.popleft()
        if dist[q] < cnt:
            continue
        for next_node in maps[q]:
            if dist[next_node] > cnt + 1:
                dist[next_node] = cnt + 1
                queue.append([next_node, cnt+1])
    if dist[end] == 1e9:
        return -1
    else:
        return dist[end]

def solution(n, roads, sources, destination):
    answer = []

    # 경로에 따른 맵 만들기
    maps = defaultdict(set)
    for r in roads:
        maps[r[0]].add(r[1])
        maps[r[1]].add(r[0])

    for s in sources:
        a = dijkstra(n, maps, s, destination)
        answer.append(a)

    return answer

 

다른 풀이 보면서 참고한 결과..

결국 목적지까지 가는데 최단 경로를 구하면 되는거라서

목적지를 시작지점으로 잡아야한다.!!

 

최종풀이

import sys
from collections import deque, defaultdict
input = sys.stdin.readline

def dijkstra(n, maps, start):
    queue = deque([[start, 0]])
    dist = [1e9 for i in range(n+1)]
    dist[start] = 0
    while queue:
        q, cnt = queue.popleft()
        if dist[q] < cnt:
            continue
        for next_node in maps[q]:
            if dist[next_node] > cnt + 1:
                dist[next_node] = cnt + 1
                queue.append([next_node, cnt+1])
    return dist

def solution(n, roads, sources, destination):
    answer = []

    # 경로에 따른 맵 만들기
    maps = defaultdict(set)
    for r in roads:
        maps[r[0]].add(r[1])
        maps[r[1]].add(r[0])

    dist = dijkstra(n, maps,destination)
    
    for i in sources:
        if dist[i] == 1e9:
            answer.append(-1)
        else:
            answer.append(dist[i])
        

    return answer

---

※ 알아야 할 것

- 다익스트라 알고리즘을 이용하자.. 한 지점에서의 최단경로를 구할 수 있음!