[프로그래머스 level2 배달] 플로이드 워셜 알고리즘 활용하기, bfs 응용(다익스트라) 버전 추가

해결해야하는 문제는 다음과 같았다.

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

 

 

이는 옛날에 풀었던 문제가 떠올랐다.

(https://kom-story.tistory.com/172?category=939435)

이 문제를 참고하였고, 그래프 형태이고, 한 지점에서 모든 경로 까지의 최단 경로를 구해야하기때문에 플로이드 워셜 알고리즘을 활용해야겠다고 생각하였다.

 

생각을 바탕으로 구현한 결과는 다음과 같다.

def solution(N, road, K):
    answer = 0
    INF = int(1e9)
    graph = [[INF]*(N+1) for i in range(N+1)]
    
    for i in range(N+1):
        for j in range(N+1):
            if i==j:
                graph[i][j] = 0
    
    for a,b,c in road :
        if graph[a][b] > c:
            graph[a][b] = c
            graph[b][a] = c
    
    for pass_through in range(1,N+1):
        for i in range(1,N+1):
            for j in range(1,N+1):
                graph[i][j] = min(graph[i][j], graph[i][pass_through]+graph[pass_through][j])
    
    
    for i in range(1,len(graph[1])) :
        if graph[1][i]<= K:
            answer += 1
    
    return answer

 

 

다른 사람들의 풀이를 보니 bfs를 응용하여 해결한 경우도 있는 것 같았다. 따라서 bfs로도 해결해보고자 혼자 생각해보았다.

(bfs에 대해 많이 부족하므로, 어떤 방식으로 접근이 가능할지 고민해보았다.)

 

 

 

def solution(N, road, K):
    answer = 0
    INF = int(1e9)
    cost = [INF] * (N+1)
    cost[1] = 0
    queue = [1]
    while queue :
        pos = queue.pop(0)
        for a,b,c in road:
            if a==pos or b==pos:
                dist = a
                if a==pos:
                    dist = b
                if c+cost[pos] < cost[dist]:
                    cost[dist] = c+cost[pos]
                    queue.append(dist)
    
    for i in cost :
        if i <= K :
            answer += 1
    return answer